92. Reverse Linked List II 反向链表I

题目

给定一个单链表 head 和两个整数 left 和 right，并且 left <= right，将 left 和 right 之间的节点反向，返回反向后的节点。

解析

题意很明确

1. 找到 left 节点和 right 节点
2. 将 left 和 right 之间的节点反向
3. 将 left 和 right 互换位置，及斩断两个节点并重新链接

最终我们需要找到四个节点的位置， left-1,left, right, right+1。分别记为
fl, l,r fr。因为已知 left 和 right，我们可以在一次遍历中完成 1和 2。

伪代码

vhead.Next=head
fl=vhead
for i:=1;i<left;i++
  fl=fl.Next
l=fl.Next
r=l
fr=r.Next
for i:=left;i<right;i++
  l = r
  fr=fr.Next
  r=r.Next
  r.Next = l

l = fl.Next
fl.Next = r
l.Next = fr

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    vhead:=&ListNode{}
    vhead.Next = head
    var f, l, r, t *ListNode
    f=vhead
    for i:=1;i<left;i++ {
        f=f.Next
    }
    l=f.Next
    r=l
    t=r.Next
    for i:=left;i<right;i++ {
        l=r
        r=t
        t=t.Next
        
        r.Next = l
    }
    l=f.Next
    f.Next = r
    l.Next = t
    return vhead.Next
}

image.png