[java/2ms] little trick on bisecting a linked list


  • 1

    make sure the #first_part >= #second.
    if the fast pointer is not null, meaning there are odd number of nodes and the slow pointer seats at the middle.

    public void reorderList(ListNode head) {
            if (head == null || head.next == null) return;
    
            // bisect the list
            ListNode pre = null;
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
    
            // if there are even number of nodes
            if (fast != null) {
                pre = slow;
                slow = slow.next;
            }
            fast = slow;
            pre.next = null;
    
            // reverse the later part
            pre = null;
            while (fast != null) {
                ListNode tmp = fast;
                fast = fast.next;
                tmp.next = pre;
                pre = tmp;
            }
    
            // insert list to first half
            fast = pre;
            slow = head;
            while (fast != null) {
                ListNode tmp = fast;
                fast = fast.next;
                tmp.next = slow.next;
                slow.next = tmp;
                slow = tmp.next;
            }
    
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.