LeetCode(100) -- 142, 143

P142. Linked List Cycle II (Medium)

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

My Solution

用hashset记录每个node，如果下一个连到已经存在的某个node，就找到了一个环。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode curr = head;
        while (curr != null) {
            if (set.contains(curr.next)) {
                return curr.next;
            }
            set.add(curr);
            curr = curr.next;
        }
        return null;
    }
}

21%

Solution

答案第一种方法跟我一样，第二种方法用了快慢指针，或者叫龟兔赛跑。

public class Solution {
    private ListNode getIntersect(ListNode head) {
        ListNode tortoise = head;
        ListNode hare = head;

        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;
            hare = hare.next.next;
            if (tortoise == hare) {
                return tortoise;
            }
        }
        return null;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode intersect = getIntersect(head);
        if (intersect == null) {
            return null;
        }

        ListNode ptr1 = head;
        ListNode ptr2 = intersect;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }
}

100%

P143. Reorder List (Medium)

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

My Solution

这道题麻烦在每次是要最后一个节点插入到前面，但是单向链表又不能从后往前。

The Best Solution

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        if (head.next == null) {
            return;
        }
        ListNode mid = findMid(head);
        ListNode next = mid.next;
        mid.next = null;

        ListNode head1 = head;
        ListNode head2 = reverse(next);

        merge(head1, head2);
    }

    private ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    private void merge(ListNode head1, ListNode head2) {
        ListNode next = head1.next;
        while (head2 != null) {
            head1.next = head2;
            head1 = head2;
            head2 = next;
            next = head1.next;
        }
    }
}