问题链接
LeetCode 24. Swap Nodes in Pairs
题目解析
给出链表,每两个节点之间交换顺序,求新的链表。
解题思路
其实不是很难,基本链表操作。直接迭代就好,注意一个问题,必须保留当前交换的两节点的前一节点指针,因为最后还得与之前链表连接上,所以最好的方法是保存前一节点指针 \(pre\),每次要交换的节点是 \(pre->next\) 和 \(pre->next->next\),另外需要注意指针的使用,最好画个图,方便理解。
参考代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *newHead = new ListNode(-1), *pre = newHead;
newHead->next = head;
while (pre->next && pre->next->next) {
ListNode *t = pre->next->next;//t=第二节点
pre->next->next = t->next;//第一节点---第三节点
t->next = pre->next;//第二节点---第一节点
pre->next = t;//上一节点---第二节点
pre = t->next;//pre=第一节点(处于第二位置)
}
return newHead->next;
}
};
递归
可能上述解法不是很好理解,不过建议理解,因为那是最基本的操作。下面的递归解法更好理解,每次将第一个节点与第三节点相连,然后第二节点与第一节点相连
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode *t = head->next;//t=第二节点
head->next = swapPairs(head->next->next);//第一节点---第三节点
t->next = head;//第二节点---第一节点
return t;
}
};
LeetCode All in One题解汇总(持续更新中...)
本文版权归作者AlvinZH和博客园所有,欢迎转载和商用,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利.