题解
- 找到中点断开,翻转后面部分,然后合并前后两个链表
- 重建该链表
两种实现方式
代码
package main type ListNode struct { Val int Next *ListNode } //找到中点断开,翻转后面部分,然后合并前后两个链表 func reorderList1(head *ListNode) { if head == nil { return } mid := findMiddle(head) tail := mid.Next mid.Next = nil tail = reverseList(tail) mergeTwoLists(head, tail) } //快慢指针找中点 func findMiddle(head *ListNode) *ListNode { slow := head fast := head.Next for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } return slow } //翻转链表 func reverseList(head *ListNode) *ListNode { curr := head var p *ListNode for curr != nil { next := curr.Next curr.Next = p p = curr curr = next } return p } //l1链表插一个,l2链表插1个,依次添加 func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} head := dummy var f bool = true for l1 != nil && l2 != nil { if f { head.Next = l1 l1 = l1.Next } else { head.Next = l2 l2 = l2.Next } f = !f head = head.Next } if l1 != nil { head.Next = l1 l1 = l1.Next head = head.Next } else if l2 != nil { head.Next = l2 l2 = l2.Next head = head.Next } return dummy.Next } //重建该链表 func reorderList2(head *ListNode) { if head == nil { return } var nodes []*ListNode for node := head; node != nil; node = node.Next { nodes = append(nodes, node) } i, j := 0, len(nodes)-1 for i < j { nodes[i].Next = nodes[j] i++ if i == j { break } nodes[j].Next = nodes[i] j-- } nodes[i].Next = nil } func main() { reorderList1(nil) reorderList2(nil) }