30. Rearrange the linked list

The first 23 God

143. Rearrange the list

Medium difficulty 633 Switch to English to receive dynamic feedback

Given a single chain table L The head node of head , Single chain list L Expressed as ：

L0 → L1 → … → Ln-1 → Ln
Please rearrange them to ：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You can't just change the value inside the node , It needs to actually exchange nodes .

Example 1:

 Input : head = [1,2,3,4]
 Output : [1,4,2,3]

Example 2:

 Input : head = [1,2,3,4,5]
 Output : [1,5,2,4,3]

Algorithm analysis

1、 Use the speed pointer , Find the central node of the linked list , It's divided into two lists

2、 Reverse the linked list on the right

3、 Merge two linked lists

The question ： Put the... Of a linked list kk Item and penultimate kk Items together .

/** * 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 ListNode middleNode(ListNode head){
    
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
    
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

  // List flip 
    public ListNode reverse(ListNode head){
    
        if(head==null||head.next==null) return head;
        ListNode tail = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }

    public ListNode merge(ListNode left,ListNode right){
    
        
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        while(left!=null&&right!=null){
    
            t.next = left;
            t = t.next;
            left = left.next;

            t.next = right;
            t = t.next;
            right = right.next;
        }
        if(left!=null){
    
            t.next = left;
            t = t.next;
            left = left.next;
        }

        if(right!=null){
    
            t.next = right;
            t = t.next;
            right = right.next;
        }
        return dummy.next;
    }
    
    public void reorderList(ListNode head) {
    
        if(head==null) return;
        ListNode middle = middleNode(head);

        ListNode left = head;
        ListNode right = reverse(middle.next);
        middle.next = null;

        head = merge(left,right);
    }
}