143. Reorder List
給定一個單鏈表的頭節點。鏈表可以表示為：
L0 → L1 → … → Ln - 1 → Ln
將鏈表重新排序為以下形式：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
你不能修改鏈表節點中的值。只能更改節點本身。
範例：
輸入：head = [1,2,3,4] 輸出：[1,4,2,3]
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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
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_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
# 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 = tmp2
24.52MB, 58ms
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head->next) {
return;
}
// Step 1: Find the middle of the linked list
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// Step 2: Reverse the second half of the linked list
ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr) {
ListNode* next_temp = curr->next;
curr->next = prev;
prev = curr;
curr = next_temp;
}
// Step 3: Merge the two halves
ListNode* first = head;
ListNode* second = prev;
while (second->next) {
ListNode* tmp1 = first->next;
ListNode* tmp2 = second->next;
first->next = second;
second->next = tmp1;
first = tmp1;
second = tmp2;
}
}
};
21.2MB, 22ms
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val === undefined ? 0 : val);
* this.next = (next === undefined ? null : next);
* }
*/
/**
* @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
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 nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// 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;
}
};
57.54MB, 81ms
