重排链表.md

重排链表

143. 重排链表

给定一个单链表 L: L0→L1→…→Ln-1→Ln ， 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值, 而是需要实际的进行节点交换:

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路:

可以发现, 这个主要分三部:

1. 找到链表的中间节点. 可以用步长分位为 1 和 2 的慢快指针;
2. 反转后半部分链表;
3. 反转后的后半部分链表逐个插入前半部分链表.

代码实现:

public class Solution {  
 public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        // 找到链表的中间节点位置
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 这里就改变了原链表 head, head是前半部分链表
        prev.next = null;
        // slow 就是后半部分的链表, 这里将后半部分链表反转. 这里利用栈
        ListNode listNode = reverseList(slow);
        
        // 这里就将两个链表合并成一个, 这里你可以新建一个链表去做, 也可以直接在 head 的上操作
        // 在 head 上操作可能会稍微复杂一些, 需要你用好几个指针来做, 不熟练的可以直接新建一个链表，因为指针指来指去的容易把自己弄迷了。
        // 利用栈也是可以实现的，这里自己可以试一下。
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while(head != null && listNode != null){
            curr.next = head;
            head = head.next;
            curr.next.next = listNode;

            listNode = listNode.next;
            curr = curr.next.next;
        }
        // 这里需要注意的是判断后半部分的链表是否为空, 可以知道链表是奇数节点还是偶数节点。
        // 如果是奇数节点的话, 链表的后半部分会比前半部分多一个节点, 因为我们把中间的那个节点算到的后半部分里面.
        if(listNode != null){
            curr.next = listNode;
        }
        head = dummy.next;
    }

    public static ListNode reverseList(ListNode head) {
        ListNode curr = head, prev = null;
        ListNode temp;
        while (curr != null) {
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}