C#LeetCode刷题之#141-环形链表（Linked List Cycle）

问题

给定一个链表，判断链表中是否有环。

进阶：

你能否不使用额外空间解决此题？

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

示例

public class Program {

    public static void Main(string[] args) {

        var head = new ListNode(1) {

            next = new ListNode(2) {

                next = new ListNode(1) {

                    next = new ListNode(2) {

                        next = new ListNode(3)

                    }

                }

            }

        };

        var res = HasCycle(head);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    private static bool HasCycle(ListNode head) {

        var pointer = head;

        while(pointer != null && pointer.next != null) {

            head = head.next;

            pointer = pointer.next.next;

            if(pointer == head) return true;

        }

        return false;

    }

    public class ListNode {

        public int val;

        public ListNode next;

        public ListNode(int x) { val = x; }

    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

False

分析：

显而易见，以上算法的时间复杂度为： $O(n)$ 。

巴特西

C#LeetCode刷题之#141-环形链表（Linked List Cycle）

最新文章

热门文章