Reorder List Problem

Asked by Amazon

Given a linked list of the form:

N0 → N1 → N2 → ....Nn-2 → Nn-1

Reorder the list in the following format:

N0 → Nn-1 → N1 → Nn-2 → N2 → ....

Example

Linked list: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
Result: 1 → 9 → 2 → 8 → 3 → 7 → 4 → 6 → 5

Linked list: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
Result: 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5

Approach

Steps

1. first find the length of list.

2. find middle index of list and using this index find the middle element.

3. store element into stack from the middle element.

4. iterate on first half of list and add stored element between 2 nodes

for the given example 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9

length = 9, mid = length/2 +1 = 5 (if length is odd)

so the mid element will be 5

we have to store mid.next to last means 6 → 7 → 8 → 9

so the stack value will be 9,8,7,6

after that iterate on first half 1 → 2 → 3 → 4 → 5

and add stack's top element between 1 and 2 and pop the element.

then the list will be

1 →9→ 2 → 3 → 4 → 5. stack values = 8,7,6

after addition jump to next node which is 2, and follow the same process

1 →9→ 2 →8→ 3 → 4 → 5 stack value = 7, 6

Time Complexity: O(n)

Space Complexity: O(n)

Code

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode reorderList(ListNode head) {
		int length = 1;
		ListNode temp = head;
		// finding the length of list
		while(temp!=null){
			length++;
			temp = temp.next;
		}
		// if length is less than 2 then no need to process further
		if(length<2)
			return head;
		
		ListNode mid = null;
		
		// finding the middle element of list
		
		int midIndex = 0;
		if(length%2==0)
		    midIndex = length/2;
		else
			midIndex = length/2 + 1;
		
		int index = 1;
		temp = head;
		// find the middle element of list
		while(index<midIndex){
			index++;
			temp = temp.next;
		}
		mid = temp.next;
		temp.next = null;
		// store into stack from the middle element of list
		
		Stack<ListNode> stack = new Stack<>();
		while(mid!=null){
			stack.push(mid);
			mid = mid.next;
		}
		temp = head;
		// add the stored element into the first half of array.
		while(stack.size()>0&&temp!=null){
			ListNode node = stack.pop();
			ListNode nextNode = temp.next;
			temp.next = node;
			node.next = nextNode;
			temp = nextNode;
		}
		return head;
	}
}