Rearrange linked list in-place

Slug: rearrange-linked-list-in-place

Difficulty: Medium

Id: 700103

Topic Tags: Linked List, Data Structures

Company Tags: None

Summary

Rearrange a given singly linked list in-place such that all even nodes are moved to the end of the list. The order of the remaining nodes should be maintained.

Detailed Explanation

To solve this problem, we can iterate through the linked list once and separate the even nodes from the odd nodes. We'll keep track of the last node of the even nodes and then append them to the end of the original list.

Here's a step-by-step breakdown:

Initialize three pointers: evenTail, oddHead, and current.
Iterate through the linked list using current. For each node:
- If the node is odd, move it to the front of the new list by updating oddHead and oddHead->next = current.
- If the node is even, update evenTail->next = current and keep track of the last even node.
After iterating through the entire list, update oddHead->next = evenTail to combine the two lists.

The time complexity for this solution is O(n), where n is the number of nodes in the linked list, since we only iterate through the list once. The space complexity is O(1) as we're not using any additional data structures that scale with the input size.

Optimized Solutions

Java

class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) return; ListNode evenTail = head, oddHead = head, current = head; while (current != null && current.next != null) { if ((current.val % 2) == 0) { evenTail = current; evenTail.next = null; } else { oddHead = current; oddHead.next = null; } current = current.next; } evenTail.next = head; } }