給定一個鍊錶,將每兩個相鄰的節點進行交換,並返回交換後的鍊錶。不能只是單純的改變節點內部的值,而是需要實際的進行節點交換。
Python
方法一 : 遞迴
算法流程:
- 如果鍊錶為空或者只有一個節點,則無需交換。
- 交換前兩個節點。
- 遞歸地對剩餘的節點進行交換。
- 遞歸地對剩餘的節點進行交換。
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 如果鍊錶為空或者只有一個節點,則無需交換
if not head or not head.next:
return head
# 交換前兩個節點
first_node = head
second_node = head.next
first_node.next = self.swapPairs(second_node.next)
second_node.next = first_node
# 返回交換後的鍊錶
return second_node
方法二:迭代兩兩交換
如果只有一個節點或者沒有節點,直接返回head。while 循環判斷當head 和head.next 都不為空的情況下
(1)tail 保存第三個及之後的鍊錶
(2)使用tmp 臨時保存head.val
(3)將head.next.val 賦予head.val 表示將後一個節點的值賦給前一個節點
(4)將tmp 賦予head.next.val 表示將前一個節點的值賦予後一個節點
這樣兩個節點的值就完成了互換判斷第三個和第四個節點是否都存在,如果是,則將tail 賦予head ,表示下一次循環交換第三個和第四個節點的值,否則直接返回result
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def swapPairs(self, head):
if not head or not head.next: return head
result = head
while head and head.next:
tail = head.next.next #tail 保存第三個及之後的鍊錶
tmp = head.val #使用tmp 臨時保存head.val
head.val = head.next.val #將head.next.val 賦予head.val 表示將後一個節點的值賦給前一個節點
head.next.val = tmp #將tmp 賦予head.next.val 表示將前一個節點的值賦予後一個節點
if tail and tail.next:
head = tail
else:
break
return result
每次記錄兩個節點數值交換,之後再將兩個節點指標往後移動
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
prev = head
cur = head.next
while prev and cur:
# 「兩兩節點的數值交換」
temp = prev.val;
prev.val = cur.val;
cur.val = temp;
if not cur.next or not cur.next.next:
break
# 「兩兩節點的鏈結」
prev = cur.next;
cur = cur.next.next;
return head
C++
遞歸:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode *res = head->next; //res指向head->next
head->next = swapPairs(head->next->next); //head.next指向遞歸
res->next = head; //res.next指向head
return res;
}
};