Skip to content

# int32bit / leetcode

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
solve.cpp

## Reverse Linked List II

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

For example: Given `1->2->3->4->5->NULL`, `m = 2` and `n = 4`,

return `1->4->3->2->5->NULL`.

Note: Given `m, n` satisfy the following condition: `1 ≤ m ≤ n ≤` length of list.

## Solution

```void reverse(ListNode *start, ListNode *end) {
if (!start || !start->next)
return;
ListNode *pre = nullptr;
ListNode *p = start;
while (p && pre != end) {
ListNode *q = p->next;
p->next = pre;
pre = p;
p = q;
}
start->next = p; // 注意最后需要更新start为end的next节点
}```

```ListNode *start = head;
ListNode *end = head;
ListNode *prev = nullptr; // 保存前一个节点，因为reverse后需要指向end节点
while (--m) {
prev = start;
start = start->next;
end = end->next;
n--;
}
while (--n) {
end = end->next;
}```

```if (prev)
prev->next = end;
else
head = end;```

## 扩展

Reverse Linked List: 逆转整个链表,实现了递归法和迭代法

You can’t perform that action at this time.