反转合并有序链表

4分钟阅读

来源：go-interview / Algorithm

给定链表 1 -> 2 -> ..、-> n-1 -> n

使用 O(1) 空间复杂度使其变为 1 -> n -> 2 -> n-1 -> ...

要在 O(1) 空间复杂度下将链表 `1 -> 2 -> ... -> n-1 -> n` 重新排列成 `1 -> n -> 2 -> n-1 -> ...`，可以采用以下方法：

解决方案

  1. 找到链表的中点：

    • 使用快慢指针方法（Floyd’s Tortoise and Hare algorithm），其中一个指针每次移动一步，另一个指针每次移动两步，直到快指针到达链表末尾。此时，慢指针指向链表的中点。

  2. 将链表分成两部分：

    • 将链表从中点断开，得到两个链表：前半部分和后半部分。中点节点可以选择断开，这样中点后的部分会成为第二部分的头节点。

  3. 反转第二部分链表：

    • 对后半部分链表进行反转。

  4. 合并两个链表：

    • 交替合并前半部分和反转后的后半部分链表。

代码实现（Python）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def reorder_list(head):
    if not head or not head.next or not head.next.next:
        return
 
    # Step 1: Find the middle of the list
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Split the list into two halves
    second_half = slow.next
    slow.next = None
    
    # Step 3: Reverse the second half of the list
    prev = None
    curr = second_half
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    second_half = prev
    
    # Step 4: Merge the two halves
    first_half = head
    while second_half:
        tmp1 = first_half.next
        tmp2 = second_half.next
        
        first_half.next = second_half
        second_half.next = tmp1
        
        first_half = tmp1
        second_half = tmp2
 
# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("None")
 
# Helper function to create a linked list from a list
def create_list(arr):
    dummy = ListNode()
    current = dummy
    for val in arr:
        current.next = ListNode(val)
        current = current.next
    return dummy.next
 
# Example usage:
arr = list(range(1, 11))  # Create a list from 1 to 10
head = create_list(arr)
print("Original list:")
print_list(head)
 
reorder_list(head)
print("Reordered list:")
print_list(head)

解释

  1. 找到链表的中点：

    • 使用快慢指针找到中点。slow 指针在链表的中点，而 fast 指针到达链表末尾。

  2. 分割链表：

    • 将链表从中点断开，形成两个链表：前半部分和后半部分。

  3. 反转后半部分链表：

    • 逐步改变链表节点的指向，完成链表的反转。

  4. 合并两个链表：

    • 交替合并两个链表，将前半部分和反转后的后半部分交替连接。

复杂度

  • 时间复杂度：O(n)，其中 n 是链表的长度。每个节点都只被访问了一次。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。

这样，你就可以在 O(1) 空间复杂度下完成链表的重新排列。

反向链接