Code Destine

Problem Statement

You have given a singly linked list :-

List = L0 –> L1 –> L2 –> L3 –> L4 … –> Ln-1 –> Ln

Reorder the given linked list to :-

List = L0 –> Ln –> L1 –> Ln-1 –> L2 –> Ln-1 ….

Example 

Input :- head = [5, 4, 10, 15, 1, 7]
Output :- [5, 7, 4, 1, 10, 15]

Solution

This problem can be solved in four steps :-

1. Find the middle node of the linked list.
2. Break the given linked list into two separate parts, first starting from the head and ending at the middle node and second starting from the node next to a middle node and ending at the last node of the linked list.
3. Reverse the second half of the linked list.
4. Traverse both linked list together and rearrange the nodes, such that the first node is from the first list and second node from the second list.

Program

public class Main {

	public static void main(String[] args) {
		
		ListNode head = null;		
		ListNode node = new ListNode(5);
		head = node;		
		node.next = new ListNode(4);
		node = node.next;		
		node.next = new ListNode(10);
		node = node.next;		
		node.next = new ListNode(15);
		node = node.next;		
		node.next = new ListNode(1);
		node = node.next;		
		node.next = new ListNode(7);	
		
		Main main = new Main();
		main.reorderList(head);
		while(head != null) {
			System.out.print(head.value + ", ");
			head = head.next;
		}
	}
	
	/* Solution */
	public void reorderList(ListNode head) {
        ListNode firstTail = mid(head);
        if (firstTail == null)
            return;
        ListNode secondHead = reverse(firstTail.next);
        firstTail.next = null;
        
        ListNode firstNext, secondNext;
        ListNode first = head;
        ListNode second = secondHead;
        while (second != null) {
            firstNext = first.next;
            secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }

    private ListNode mid(ListNode head) {
        if (head == null || head.next == null || head.next.next == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }   

    private ListNode reverse(ListNode head) {
        ListNode next = null;
        ListNode previous = null;
        ListNode current = head;
        while(current != null) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

5, 7, 4, 1, 10, 15, 

That’s all for Reorder a Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.