Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

143. Reorder List

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.

Example 1:

1
2
Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

1
2
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

如果單純list,穿插就想到zip,反向就想到[::-1],但這題是linkedlist,可以用快慢指針。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
# def init(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return []

# Find the middle of the list
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next

slow.next,mid = None,slow.next # del last, mid=last node

# Reverse the half after middle
dummyHead = ListNode(0)
while mid:
print(mid.val)
dummyHead.next, mid.next, mid = mid, dummyHead.next, mid.next

# Start reorder one by one
reverse = dummyHead.next
while reverse:
head.next,reverse.next,reverse,head = reverse,head.next,reverse.next,head.next

如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Welcome to my other publishing channels