Question

143. Reorder List

Solution

题目大意：给一个链表，将这个列表分成前后两部分，后半部分反转，再将这两分链表的节点交替连接成一个新的链表

思路 ：先将链表分成前后两部分，将后部分链表反转，再将两部分链表连接成一个新链表

链表取中间节点思路：龟兔赛跑，每秒钟乌龟跑1步，兔子跑2步，当兔子跑完全程时乌龟正好跑完一半

链表反转实现思路 ：

Java实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        ListNode mid = findMid(head);
        ListNode l2 = mid.next;
        mid.next = null; // 将前半部分链表截断
        l2 = reverse(l2); // 将后半部分链表反转
        ListNode l1 = head;
        // 组装新的链表
        while (l1 != null && l2 != null) {
            ListNode tmp = l1.next;
            l1.next = l2;
            l2 = l2.next;
            l1.next.next = tmp;
            l1 = tmp;
        }
    }
    
    // 返回链表的中间节点
    // 龟兔赛跑，每秒钟乌龟跑1步，兔子跑2步，当兔子跑完全程时乌龟正好跑完一半
    ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    
    // 返回反转后的链表
    ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}