LeetCode题解|143. Reorder List

题目链接：143. Reorder List

概述

给定一个单链表L: L₀→L₁→…→L_n-1→L_n，将其重排为：L₀→L_n→L₁→L_n-1→L₂→L_n-2→…，即将L头尾交替重排序。

思路

整体四里路为：先将L一分为二，然后将后半段链表逆序，再依次插入前半段节点中。

在找链表的中间节点时，使用快慢指针就可以快速找到。

逆序时，将当前节点的后继节点进行位置交换，举例来说，给定链表l:head→b→c→d。首先，将b的后继，改为原后继c的后继d，即：head→b→d，然后将c指向b，head指向c，即：head→c→b→d

实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    if(head == null || head.next == null){
        return;
    }
    var fast = head,
        slow = head;
    
    // 找到中间节点
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    
    var middle = slow,
        cur = slow.next;
    
    // 反转后半段链表
    while(cur.next != null){
        var tmp = cur.next;
        cur.next = tmp.next;
        tmp.next = middle.next;
        middle.next = tmp;
    }
    
    // 拼接
    var p1 = head,
        p2 = slow.next;
    while(p1 != slow){
        slow.next = p2.next;
        p2.next = p1.next;
        p1.next = p2;
        p1 = p2.next;
        p2 = slow.next;
    }
};

题解合集