92.M 反转链表 II

Problem: 92. 反转链表 II

思路

为了简化处理，构造一个虚拟节点。

先把需要反转的部分找到，并且记录反转部分的前驱和后继节点

把需要反转的部分截取出来，然后做反转，最后再用前驱和后继节点把反转部分拼回去

Code

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || left == right {
		return head
	}

	// 构造虚拟节点，简化处理
	var dummy = &ListNode{Val: -1, Next: head}
	pre := dummy
	for i := 1; i < left; i++ {
		pre = pre.Next
	}

	// 需要反转的链表的头结点
	start := pre.Next

	// 需要反转的链表的尾节点
	end := start
	for i := left; i < right; i++ {
		end = end.Next
	}

	// 记录反转的链表的尾节点的下一个节点
	next := end.Next

	// 截断链表
	end.Next = nil

	// 反转子链表
	partHead := reverse(start)

	// 重新连接
	pre.Next = partHead
	start.Next = next
	return dummy.Next
}

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

	return pre
}