0092.reverse-linked-list-ii.md

0092.Reverse-Linked-List-II

Description

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list. Note: 1 ≤ m ≤ n ≤ length of list. Example 1:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Tags: Linked List

题意

给定一个单链表和两个数字 m 和 n，反转链表 m 到 n 的部分。 请将链表中第 nn 个节点和第 mm 个节点之间的部分翻转。 链表最多只能遍历一遍。

题解

思路1

1. 链表先走 m 步，到达开始反转的起点，并记录下前一个节点和反转开始的节点。
2. 开始反转链表，反转的长度位 n - m。
3. 把链表连起来。

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    newHead := new(ListNode)
    newHead.Next = head
    current := newHead 
    for i := 0; i < m - 1; i++ {
       current = current.Next
    }

    prev := current
    current = current.Next
    for i := 0; i < n - m; i++ {
       node := &ListNode{current.Next.Val, prev.Next}
       prev.Next = node
       current.Next = current.Next.Next
    }
    return newHead.Next
}

思路2

思路2 ```go

```

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm