leetcode143 重排链表

题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

解析

这道题相当于三题合一，先通过快慢指针找到链表的中间节点，然后反转中间节点到末尾的这一段链表，再然后遍历，将每个节点的next指向合适的位置即可

func reorderList(head *ListNode) {
mid := middleNode(head)
head2 := reverseList(mid)
for head2.Next != nil {
next := head.Next
next2 := head2.Next
head.Next = head2
head2.Next = next
head = next
head2 = next2
}
}

func middleNode(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}

func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}

原文地址：https://blog.csdn.net/midi666/article/details/137764776

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！