LeetCode - Reorder List

Problem description

description

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3. Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Analysis

Basically, we can split the LinkedList into two List and reverse the second one and merge them.

/**
 * 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){
            return;
        }
        
        int size = 0;
        
        ListNode p = head;
        while(p!=null){
            p = p.next;
            size++;
        }
        
        int len1 = size - size/2;
        
        p = head;
        while(len1 > 1){
            p = p.next;
            len1--;
        }
        
        ListNode second = p.next;
        p.next = null;
        
        second = reverse(second);
        
        p = head;
        while(second != null){
            ListNode next = second.next;
            second.next = p.next;
            p.next = second;
            p = second.next;
            second = next;
        }
    }
    
    ListNode reverse(ListNode node){
        if (node == null){
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = node;
        
        ListNode p = dummy.next;
        
        while (p.next != null){
            ListNode next = p.next.next;
            p.next.next = dummy.next;
            dummy.next = p.next;
            p.next = next;
        }
        
        return dummy.next;
    }
}

For the reverse part

// reverse the second part of the list [Problem 206]
// convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4
// reverse the second half in-place
ListNode prev = null, curr = slow, tmp;
while (curr != null) {
  tmp = curr.next;

  curr.next = prev;
  prev = curr;
  curr = tmp;
}

What to improve

• for the reverse part, need to be more familiar with that.

• to get the half of the list, we can use fast and slow pointer to do that.