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.next
C++
這個解法首先創建了一個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;
}
};