Leetcode题143、重排链表（Python题解）

it2023-03-01 93

问题：

题目来源：力扣（LeetCode）

leetcode143.重排链表

难度：中等

分析：这道题是链表题目训练题的合集吧哈哈，常见的链表操作都有体现。方法一：将链表节点用数组保存下来，然后按照题目顺序重新连接起来。注意存的是节点，而不是链表的值，因为题目要求不能只改变链表值。方法二：先寻找链表中点，再对链表后半部进行翻转，然后合并链表。好家伙！一道顶三道，寻找链表中点，翻转链表，合并链表，打包放送。

解决方法： 1：列表存节点+双指针

#列表存储 class Solution: def reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if not head: return nodes = [] node = head while node: nodes.append(node) node = node.next i, j = 0, len(nodes) - 1 while i < j: nodes[i].next = nodes[j] i += 1 if i == j: break nodes[j].next = nodes[ j -= 1 nodes[i].next = None

2：寻找中点+翻转链表+合并链表

#寻找中点，翻转后半链表，合并链表 class Solution: def reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if not head: return mid = self.middleNode(head) l1 = head l2 = mid.next mid.next = None l2 = self.reverseList(l2) self.mergeList(l1, l2) def middleNode(self, head): slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def reverseList(self, head): prev = None cur = head while cur: temp = cur.next cur.next = prev prev = cur cur = temp return prev def mergeList(self, l1, l2): while l1 and l2: l1_temp = l1.next l2_temp = l2.next l1.next = l2 l1 = l1_temp l2.next = l1 l2 = l2_temp