Description
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Examples:
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]Solution in Python
To solve the problem of reordering a linked list in Python, we can follow these steps:
- Find the middle of the linked list: Use the fast and slow pointer technique to find the middle of the linked list.
- Reverse the second half of the linked list: Reverse the second half of the list starting from the middle.
- Merge the two halves: Merge the first half and the reversed second half alternatively.
Python
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return
# Step 1: Find the middle of the linked list using slow and fast pointers
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse the second half of the linked list
prev, curr = None, slow
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
# Step 3: Merge the two halves
first, second = head, prev
while second.next:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2Detailed Explanation:
- Find the Middle of the Linked List:
- Use two pointers,
slowandfast. Moveslowone step at a time andfasttwo steps at a time. - When
fastreaches the end,slowwill be at the middle of the list.
- Use two pointers,
- Reverse the Second Half of the Linked List:
- Start from the middle node (found in step 1) and reverse the nodes until the end of the list.
- Use three pointers,
prev,curr, andnext_node, to reverse the links between the nodes.
- Merge the Two Halves:
- Use two pointers,
firststarting from the head andsecondstarting from the reversed middle. - Alternate the nodes from
firstandsecondto form the required reordered list.
- Use two pointers,
Solution in Javascript
JavaScript
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
if (!head || !head.next) return;
// Step 1: Find the middle of the linked list using slow and fast pointers
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the linked list
let prev = null;
let curr = slow;
while (curr !== null) {
let nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
// Step 3: Merge the two halves
let first = head;
let second = prev;
while (second.next !== null) {
let tmp1 = first.next;
let tmp2 = second.next;
first.next = second;
second.next = tmp1;
first = tmp1;
second = tmp2;
}
};Solution in Java
Java
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
// Step 1: Find the middle of the linked list using slow and fast pointers
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the linked list
ListNode prev = null;
ListNode curr = slow;
while (curr != null) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
// Step 3: Merge the two halves
ListNode first = head;
ListNode second = prev;
while (second.next != null) {
ListNode temp1 = first.next;
ListNode temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}
}Solution in C#
C#
public class Solution {
public void ReorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
// Step 1: Find the middle of the linked list using slow and fast pointers
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the linked list
ListNode prev = null;
ListNode curr = slow;
while (curr != null) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
// Step 3: Merge the two halves
ListNode first = head;
ListNode second = prev;
while (second.next != null) {
ListNode temp1 = first.next;
ListNode temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}
}