Description#
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:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 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 <= 5001 <= left <= right <= n
Follow up: Could you do it in one pass?
Solutions#
Solution 1: Simulation#
Define a dummy head node dummy, pointing to the head node head of the linked list. Then define a pointer pre pointing to dummy. Start traversing the linked list from the dummy head node. When you traverse to the left node, point pre to this node. Then start traversing right - left + 1 times from this node, and insert the nodes you traverse into the back of pre. Finally, return dummy.next.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the linked list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| # 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]:
if head.next is None or left == right:
return head
dummy = ListNode(0, head)
pre = dummy
for _ in range(left - 1):
pre = pre.next
p, q = pre, pre.next
cur = q
for _ in range(right - left + 1):
t = cur.next
cur.next = pre
pre, cur = cur, t
p.next = pre
q.next = cur
return dummy.next
|
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.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head.next == null || left == right) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
for (int i = 0; i < left - 1; ++i) {
pre = pre.next;
}
ListNode p = pre;
ListNode q = pre.next;
ListNode cur = q;
for (int i = 0; i < right - left + 1; ++i) {
ListNode t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
p.next = pre;
q.next = cur;
return dummy.next;
}
}
|
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.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head->next || left == right) {
return head;
}
ListNode* dummy = new ListNode(0, head);
ListNode* pre = dummy;
for (int i = 0; i < left - 1; ++i) {
pre = pre->next;
}
ListNode *p = pre, *q = pre->next;
ListNode* cur = q;
for (int i = 0; i < right - left + 1; ++i) {
ListNode* t = cur->next;
cur->next = pre;
pre = cur;
cur = t;
}
p->next = pre;
q->next = cur;
return dummy->next;
}
};
|
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
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head.Next == nil || left == right {
return head
}
dummy := &ListNode{0, head}
pre := dummy
for i := 0; i < left-1; i++ {
pre = pre.Next
}
p, q := pre, pre.Next
cur := q
for i := 0; i < right-left+1; i++ {
t := cur.Next
cur.Next = pre
pre = cur
cur = t
}
p.Next = pre
q.Next = cur
return dummy.Next
}
|
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
| /**
* 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 n = right - left;
if (n === 0) {
return head;
}
const dummy = new ListNode(0, head);
let pre = null;
let cur = dummy;
for (let i = 0; i < left; i++) {
pre = cur;
cur = cur.next;
}
const h = pre;
pre = null;
for (let i = 0; i <= n; i++) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
h.next.next = cur;
h.next = pre;
return dummy.next;
}
|
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
| // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn reverse_between(
head: Option<Box<ListNode>>,
left: i32,
right: i32
) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
let mut pre = &mut dummy;
for _ in 1..left {
pre = &mut pre.as_mut().unwrap().next;
}
let mut cur = pre.as_mut().unwrap().next.take();
for _ in 0..right - left + 1 {
let mut next = cur.as_mut().unwrap().next.take();
cur.as_mut().unwrap().next = pre.as_mut().unwrap().next.take();
pre.as_mut().unwrap().next = cur.take();
cur = next;
}
for _ in 0..right - left + 1 {
pre = &mut pre.as_mut().unwrap().next;
}
pre.as_mut().unwrap().next = cur;
dummy.unwrap().next
}
}
|
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
| /**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function (head, left, right) {
if (!head.next || left == right) {
return head;
}
const dummy = new ListNode(0, head);
let pre = dummy;
for (let i = 0; i < left - 1; ++i) {
pre = pre.next;
}
const p = pre;
const q = pre.next;
let cur = q;
for (let i = 0; i < right - left + 1; ++i) {
const t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
p.next = pre;
q.next = cur;
return dummy.next;
};
|
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
| /**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseBetween(ListNode head, int left, int right) {
if (head.next == null || left == right) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
for (int i = 0; i < left - 1; ++i) {
pre = pre.next;
}
ListNode p = pre;
ListNode q = pre.next;
ListNode cur = q;
for (int i = 0; i < right - left + 1; ++i) {
ListNode t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
p.next = pre;
q.next = cur;
return dummy.next;
}
}
|
