链表系列一＞重排链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        //边界
        if (head == null || head.next == null || head.next.next == null) return;

        ListNode fast = head,slow = head;

        //1.找链表的中间节点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //2.把 slow 后面的部分链表给逆序 - 头插法
        ListNode prev = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;//把两个链表断开

        while(cur != null){
            //记录cur后的节点，不然后面就断开了
            ListNode next = cur.next;
            cur.next = prev.next;
            prev.next = cur;
            cur = next;
        }

        //3.合并两个链表(第一个头--》head, 第二个的头--》prev)
        ListNode tmp = new ListNode(0);
        ListNode cur1 = head,cur2 = prev.next;
        ListNode curN = tmp;

        while(cur1 != null){
            curN.next = cur1;
            curN = cur1;
            cur1 = cur1.next;

            if(cur2 != null){
                curN.next = cur2;
                curN = cur2;
                cur2 = cur2.next;
            }
        
        }
    }
}