链表中点查找、链表反转、链表合并。
题目 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
题解 方法一：线性表 因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。
因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class ListNode : def __init__ (self, x) : self.val = x self.next = None def createLink_rearinsert (lista) : head = ListNode(-1 ) rear = head for i in lista: new_node=ListNode(i) rear.next=new_node rear=new_node return head.next class Solution : def reorderList (self, head: ListNode) -> None : if not head: return vec = list() node = head while node: vec.append(node) node = node.next i, j = 0 , len(vec) - 1 while i < j: vec[i].next = vec[j] i += 1 if i == j: break vec[j].next = vec[i] j -= 1 vec[i].next = None return head if __name__=="__main__" : head = [1 ,2 ,3 ,4 ] new_a=createLink_rearinsert(head) a1 = Solution() p=a1.reorderList(new_a) list_head=[] while p!=None : list_head.append(p.val) p=p.next print(list_head)
[1, 4, 2, 3]复杂度分析
时间复杂度：O(N)，其中 N是链表中的节点数。
空间复杂度：O(N)，其中 N 是链表中的节点数。主要为线性表的开销。
方法二：寻找链表中点 + 链表逆序 + 合并链表 注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
这样我们的任务即可划分为三步：
找到原链表的中点
我们可以使用快慢指针来 O(N) 地找到链表的中间节点。
将原链表的右半端反转
将原链表的两端合并。
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 class ListNode : def __init__ (self, x) : self.val = x self.next = None def createLink_rearinsert (lista) : head = ListNode(-1 ) rear = head for i in lista: new_node=ListNode(i) rear.next=new_node rear=new_node return head.next class Solution : def reorderList (self, head: ListNode) -> None : if not head or not head.next: return tmp_head=ListNode(-1 ) ptr=head rear =tmp_head left_rear,right_start=self.list_in_node(head) if left_rear==right_start: right_ptr= self.reverse_link(right_start.next) while ptr and right_ptr: rear.next=ptr ptr=ptr.next rear=rear.next rear.next=right_ptr right_ptr=right_ptr.next rear=rear.next rear.next=left_rear rear.next.next=None else : right_ptr=self.reverse_link(right_start) while ptr and right_ptr: rear.next=ptr ptr=ptr.next rear=rear.next rear.next=right_ptr right_ptr=right_ptr.next rear=rear.next rear.next=None head=tmp_head.next return head def list_in_node (self,head) : slow =head fast=head.next while fast!=None and fast.next!=None : fast=fast.next.next slow =slow.next if not fast: left_rear=slow right_start=slow else : left_rear = slow right_start=slow.next return left_rear,right_start def reverse_link (self,head) : prev=head cur=head.next while cur!=None : third=cur.next cur.next=prev prev=cur cur=third head.next=None return prev if __name__=="__main__" : head = [1 ,2 ,3 ,4 ,5 ] new_a=createLink_rearinsert(head) a1 = Solution() p=a1.reorderList(new_a) list_head=[] while p!=None : list_head.append(p.val) p=p.next print(list_head)
[1, 5, 2, 4, 3]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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class Solution : def reorderList (self, head: ListNode) -> None : if not head: return mid = self.middleNode(head) l1 = head l2 = mid.next mid.next = None l2 = self.reverseList(l2) self.mergeList(l1, l2) return head def middleNode (self, head: ListNode) -> ListNode: slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def reverseList (self, head: ListNode) -> ListNode: prev = None curr = head while curr: nextTemp = curr.next curr.next = prev prev = curr curr = nextTemp return prev def mergeList (self, l1: ListNode, l2: ListNode) : while l1 and l2: l1_tmp = l1.next l2_tmp = l2.next l1.next = l2 l1 = l1_tmp l2.next = l1 l2 = l2_tmp if __name__=="__main__" : head = [1 ,2 ,3 ,4 ,5 ] new_a=createLink_rearinsert(head) a1 = Solution() p=a1.reorderList(new_a) list_head=[] while p!=None : list_head.append(p.val) p=p.next print(list_head)
[1, 5, 2, 4, 3]
