LeetCode 24. Swap Nodes in Pairs

时间:2022-09-14 11:39:00

问题链接

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和博客园所有,欢迎转载和商用,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利.