leetcode-92-Reverse-Linked-List-II

描述


Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

img

1
2
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

1
2
Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Follow up: Could you do it in one pass?

分析


反转链表的题目,适合练习。相关题是206

解决方案1(Python)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
def reverseLinkedList(head: ListNode):
pre = None
current = head
while current:
next = current.next
current.next = pre
pre = current
current = next
dummy = ListNode(-1)
dummy.next = head

pre = dummy
for _ in range(left-1):
pre = pre.next
right_node = pre
for _ in range(right-left+1):
right_node = right_node.next
left_node = pre.next
current = right_node.next

pre.next = None
right_node.next = None

reverseLinkedList(left_node)
pre.next = right_node
left_node.next = current
return dummy.next

解决方案2(Golang)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/

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

func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummyNode := &ListNode{Val: -1}
dummyNode.Next = head

pre := dummyNode
for i := 0; i < left-1; i++ {
pre = pre.Next
}

rightNode := pre
for i := 0; i < right-left+1; i++ {
rightNode = rightNode.Next
}

leftNode := pre.Next
current := rightNode.Next

pre.Next = nil
rightNode.Next = nil
reverseLinkedList(leftNode)

pre.Next = rightNode
leftNode.Next = current
return dummyNode.Next
}

相关问题


题目来源