题目标题

重排链表

参考解析
  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, val=0, next=None):
  4. # self.val = val
  5. # self.next = next
  6. class Solution:
  7. def reorderList(self, head: ListNode) -> None:
  8. """
  9. Do not return anything, modify head in-place instead.
  10. """
  11. if not head:
  12. return head
  13. mid = self.findMid(head)
  14. tail = self.reverseList(mid.next)
  15. mid.next = None
  16. dummy = ListNode()
  17. dummy.next = head
  18. cur = dummy
  19. while head and tail:
  20. cur.next = head
  21. cur = cur.next
  22. head = head.next
  23. cur.next = tail
  24. cur = cur.next
  25. tail = tail.next
  26. if head:
  27. cur.next = head
  28. return dummy.next
  29. def findMid(self, head):
  30. slow = fast = head
  31. while fast and fast.next:
  32. slow = slow.next
  33. fast = fast.next.next
  34. return slow
  35. def reverseList(self, head):
  36. pre, cur = None, head
  37. while cur:
  38. cur.next, pre, cur = pre, cur, cur.next
  39. return pre