C#LeetCode刷题之#141-环形链表(Linked List Cycle)

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)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3901

发表评论

登录后才能评论