DEV Community

Dev Nirwal
Dev Nirwal

Posted on

Reorder List: LC 143 medium, GFG hard

Problem Link: Leetcode, Geeks for geeks

Intuition

We need to divide two pointers one at start and one at bottom

Approach

Step 1: first find the mid point of the linked list using slow-fast pointer approach.

Step 2: Divide the linked list into two two by two pointers firstHalf and secondHalf.

Step 3: Use reverse() to reverse the second half of the list.

Step 4: For the final step combined the reversed second half and first half to get the final result.

Complexity

  • Time complexity: O(N)

  • Space complexity: O(1)

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 ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head.next;
        while(next!=null){
            curr.next = prev;
            prev = curr;
            curr = next;
            next = next.next;
        }
        curr.next = prev;
        return curr;
    }
    public void reorderList(ListNode head) {
        if(head == null || head.next == null ) return;
        // use turtle rabbit method, slow-fast pointer to find middle of the linkedlist 
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next; // move once
            fast = fast.next.next; // move twice faster 
        }
        // Divide the linkedList into two parts;
        ListNode secondHalf = slow.next;
        // Set first half next to null to deattach the flist 
        slow.next = null;
        // reverse the second half
        secondHalf = reverse(secondHalf);
        ListNode firstHalf  = head;
        ListNode temp = secondHalf;
        // combinig both list
        while(secondHalf!=null){
            temp = temp.next;
            secondHalf.next = firstHalf.next;
            firstHalf.next  = secondHalf;
            firstHalf = secondHalf.next;
            secondHalf = temp;
        }
        return;
    }
}
Enter fullscreen mode Exit fullscreen mode

GitHub repo for more solutions: Git

Leetcode profile: Leetcode: devn007

Geeks for geeks profile: GFG: devnirwal16

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more