Linked lists: rearranging linked lists

subject

https://leetcode-cn.com/problems/LGjMqU/
Enter a linked list , Rearrange the node order of the linked list . for example ：

Their thinking

According to the meaning , Divide the list into two parts , The first half and the second half .

Reverse the second half of the list , Then merge with the first half of the linked list , You can get the rearranged linked list .

The specific process is divided into 3 Step ：
1. Find the first half of the linked list . utilize Speed pointer , The quick pointer goes first every time 2 Step , In addition, slow down the pointer by one step , When the block pointer goes to the end , The slow pointer just reaches the middle node of the linked list .
2. Put the second half List reversal .
3. Merge The first half and the reverse second half are linked .

The specific code is as follows ：

Code

/** * 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) {
    
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        // Find the last node in the first half .
        while(fast != null && fast.next != null) {
    
            slow = slow.next;
            fast = fast.next;
            if(fast.next != null) {
    
                fast = fast.next;
            }
        }
         ListNode temp = slow.next;
         slow.next = null;
         // Merge list 
         link(head, reverseList(temp), dummy);
    }

    private void link(ListNode node1, ListNode node2, ListNode head) {
    
        //1 2 3
        //5 4
        ListNode pre = head; // The sentinel node , Used to merge linked lists .
        while(node1 != null && node2 != null) {
    
            ListNode temp = node1.next;
 
            pre.next = node1;
            node1.next = node2;
            pre = node2;

            node1 = temp;
            node2 = node2.next;
        }
        if(node1 != null){
     // When the linked list is an odd number , Judge the tail node of the first half .
            pre.next = node1;
        }
       
    }

    private ListNode reverseList(ListNode head) {
    
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
    
            ListNode temp = cur.next;
            cur.next = pre;
            pre =  cur;
            cur = temp;
        }
        return pre;
    }
}

summary

The problem is to rearrange the linked list , The law can be found by observing the case list , You only need to find the middle node of the linked list with the help of the fast and slow pointer , Reverse the second half of the list , Merge the first half of the linked list , You can get the answer .