双指针解决链表问题

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解题思路：
利用快慢指针的思想，慢指针slow每次走一步，快指针fast每次走两步，如果链表中有环，则快慢指针一定会相遇，此时slow = fast。如果链表中没有环，fast一定会指向null。

public boolean hasCycle(ListNode head) {

    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

---

142.环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表

解题思路：
我们需要在141题的思路上进一步扩展。首先我们和上题一样判断slow和fast指针是否能够相遇。如果不相遇，则链表无环，直接返回null。当相遇时，我们需要进行进一步处理。

我们设入环的第一个节点到快慢指针相遇的节点长度为k，从头节点到快慢指针相遇的节点长度为m。

则从头节点到入环的第一个节点长度为m-k。此时fast指针在走m-k步就可以到入环的第一个节点。所以我们让slow重新指回头节点。slow和fast再次相遇的节点就是入环的第一个节点。

public ListNode detectCycle(ListNode head) {

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            break;
        }
    }

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

    return null;
}

---

160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解题思路：
我们设链表A的长度为a，链表B的长度为b，相交链表的长度为c。

让指针listA从headA节点出发走a下，走到null后，将指针指向headB继续走。

让指针listB从headB节点出发走b下，走到null后，将指针指向headA继续走。

当listA和listB相遇时，这个就是他们的相交节点。此时他们都走了a + b - c的长度。

如果没有相交节点，c = 0， 此时他们都走了a + b的长度，指针都指向null。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    ListNode listA = headA;
    ListNode listB = headB;

    while (listA != listB) {
        listA = (listA != null) ? listA.next : headB;
        listB = (listB != null) ? listB.next : headA;
    }

    return listA;
}

---

19.删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路：
要删除倒数第n个结点，就需要找到倒数第n-1个结点。

设置快慢指针slow和fast。我们需要让slow指向第n-1个结点，就要让fast先走n-1步。

注意，因为要考虑特殊情况，当节点数量为1，我们需要删除头节点，就需要建立一个空节点作为新的头节点，fast和slow从空节点开始，就需要走n步。终结条件为fast为空或者fast.next为空。

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode dummyHead = new ListNode();
    dummyHead.next = head;

    ListNode slow = dummyHead, fast = dummyHead;

    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;

    return dummyHead.next;
}

---

21.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：
递归解法：
对于递归解法，我们不要深入递归去考虑，只需要考虑某个时间的状态。

假设现在有两个节点，list1和list2。对于初始状态，如果list1或list2为空，则直接返回非空的那一个。

//我们先定义方法的意义和返回值
//定义这个方法可以得到合并后的结果
public ListNode mergeTwoLists(ListNode list1, ListNode list2)

如果两个节点都不为空，我们就需要将两个节点中较小的一个，指向已合并好的递归结果

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    if (list1 == null || list2 == null) {
        return (list1 != null) ? list1 : list2;
    }

    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

迭代解法：
用两个指针cur1，cur2分别指向list1，list2。用cur指针记录串联新的链表，用dummyHead记录新的头节点作为返回值。
当cur1，cur2都不为空时，我们比较cur1和cur2的大小，cur指向较小的一个，并且让cur和较小的节点移动一位。

最后让cur指向非空的cur1或者cur2即可。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    ListNode dummyHead = new ListNode();
    ListNode cur = dummyHead;
    ListNode cur1 = list1, cur2 = list2;

    while (cur1 != null && cur2 != null) {
        
        if (cur1.val <  cur2.val) {
            cur.next = cur1;
            cur1 = cur1.next;
        } else {
            cur.next = cur2;
            cur2 = cur2.next;
        }
        cur = cur.next;
    }

    cur.next = (cur1 != null) ? cur1 : cur2;

    return dummyHead.next;
}

---

23.合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解题思路：
我们可以把合并K个升序链表转化为合并两个有序链表的问题。回忆一下归并排序，在合并的时候，就是K个有序数组合并成一个有序数组。我们可以借助归并排序的思想。将合并K个升序链表转化为O（knlogk）的问题。

public ListNode mergeKLists(ListNode[] lists) {

    return merge(lists, 0, lists.length - 1);
}

public ListNode merge(ListNode[] lists, int left, int right) {

    if (left > right) {
        return null;
    } else if (left == right) {
        return lists[left];
    } else {
        int mid = left + (right - left) / 2;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    if (l1 == null || l2 == null) {
        return l1 != null ? l1 : l2;
    }

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }        
}

---

86.分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

解题思路:
我们用两个节点cur1和cur2分别记录小于x的节点和大于或等于x的节点,用cur记录head节点。在用dummy1和dummy2记录分别的头节点。遍历head链表，最后令cur1.next指向dummy2.next即可。

public ListNode partition(ListNode head, int x) {

   ListNode dummy1 = new ListNode();
   ListNode dummy2 = new ListNode();
   ListNode cur1 = dummy1, cur2 = dummy2;
   ListNode cur = head;

   while (cur != null) {
       if (cur.val < x) {
           cur1.next = cur;
           cur1 = cur1.next;
       } else {
           cur2.next = cur;
           cur2 = cur2.next;
       }
       cur = cur.next;
   }

   cur2.next = null;
   cur1.next = dummy2.next;

   return dummy1.next;
}

---

876.链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

解题思路
使用快慢指针，slow和fast。fast每次走两步，slow每次走一步即可。

因为题目中说如果有两个中间结点，则返回第二个中间结点。所以无论链表的结点个数为单数还是复数，这种方法都可以返回正确结果。

public ListNode middleNode(ListNode head) {

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}