024 Swap Nodes in Pairs[M]

1 題目描述

Given a linked list, swap every two adjacent nodes and return its head.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

難度：Medium

2 題目樣例

For example,Given 1->2->3->4, you should return the list as 2->1->4->3.

3 題意分析

這道題目是想讓你成對交換鏈表中的節點。

不算難，屬於基本的鏈表題目。

4 思路分析

可以利用回溯的思想，每次都遞歸遍歷到鏈表末尾，先交換鏈表最後兩個節點，然後依次向前操作。

用遞歸寫出來的代碼十分簡潔。

代碼實現如下：

class Solution { public: ListNode* swapPairs(ListNode* head) { if (!head || !head->next) return head; ListNode *t = head->next; head->next = swapPairs(head->next->next); t->next = head; return t; }};

也可以利用迭代的方法進行實現，直接按照題目說的去操作就行了。

5 後記

最近的題目多數都是數據結構題目而不是演算法題目欸......

數據結構蒟蒻表示瑟瑟發抖，並且留下了悔恨（當年沒好好學）的眼淚。QAQ