反转链表 II

206. 反转链表 II

leetcode 链接

思路：

1.使用 dummy 节点，dummy.next 指向 head 节点。

2.从 0 循环 left-1 次，找到 left 节点的前一个节点，当前 pre 节点指向 left 节点的前一个节点。

3.将 left 的第一个节点设为 current，然后从 left 循环到 right，每次循环将 current.next 节点缓存为 next, 然后 current.next 指向 next.next, 然后 next.next 指向 pre.next, 然后 pre.next 指向 next.

4.循环完毕之后直接返回 dummy.next 即可。

typescript 解法

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  const dummy: ListNode = new ListNode(-1, head);
  let pre: ListNode = dummy;
  for (let i = 1; i < left; i++) {
    pre = pre.next;
  }
  let current: ListNode = pre.next;
  for (let i = 0; i < right - left; i++) {
    const next = current.next;
    current.next = next.next;
    next.next = pre.next;
    pre.next = next;
  }
  return dummy.next;
}

go 解法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    dummy := &ListNode {
        Next: head,
    }
    pre := dummy
    // 获取到left位置的左边一个节点
    for i := 1 ; i < left; i ++ {
        pre = pre.Next
    }
    current := pre.Next

    for i := 0; i < right - left; i ++ {
        next := current.Next
        current.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return dummy.Next
}