Reverse Linked List II : 將linked list的第m–n個元素進行翻轉
Python
迭代
- 定義一個函數，該函數需要輸入linked list的頭結點和要反轉的兩個節點（m和n）。
- 找到linked list中第m-1個節點（pre_node）和第n個節點（end_node）。
- 將第m個節點到第n-1個節點反轉，同時記錄下第m個節點（start_node）和第n個節點的後繼節點（succ_node）。
- 將pre_node的後繼指向end_node，將start_node的後繼指向succ_node。
- 返回反轉後的linked list的頭節點。
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head or not head.next:
return head
# 定義頭linked list
dummy = ListNode(-1)
dummy.next = head
# 找到第m-1個節點
pre_node = dummy
for i in range(m - 1):
pre_node = pre_node.next
# 紀錄第m個節點
start_node = pre_node.next
# 反轉第m個節點到第n個節點
end_node = start_node
succ_node = start_node.next
for i in range(n - m):
temp = succ_node.next
succ_node.next = end_node
end_node = succ_node
succ_node = temp
# 將pre_node的後繼指向end_node，將start_node的後繼指向succ_node
pre_node.next = end_node
start_node.next = succ_node
return dummy.nextC++
這個解法首先創建了一個dummy節點，指向鍊錶的頭節點。然後我們需要找到需要翻轉的鍊錶的起始位置和終止位置，即left和right。我們將指針pre指向dummy節點，然後將pre移動到需要翻轉的鍊錶的起始位置前一個節點。接著，我們將指針cur指向pre的下一個節點，開始進行鍊錶翻轉。
我們使用next指針來記錄cur的下一個節點，然後將cur的next指針指向next的下一個節點，這樣就將next節點從鍊錶中取出來了。然後，我們將next節點插入到pre的後面，即pre->next位置。然後，我們將指針cur指向pre的後一個節點，繼續進行翻轉操作，直到翻轉到鍊錶的終止位置。
最後，我們返回dummy->next節點，即翻轉後的鍊錶頭節點。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head || !head->next) return head;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
for (int i = 1; i < left; i++) pre = pre->next;
ListNode* cur = pre->next;
for (int i = left; i < right; i++) {
ListNode* next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummy->next;
}
};