LeetCode 题解

积跬步，至千里。

两两交换链表中的节点

分类：LeetCode 标签： 链表 发布于：2019-10-20 ID：24

题目描述

来源于 https://leetcode-cn.com/

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解法一

使用栈。这个方法可以解决，k 个一组进行翻转的问题。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        ListNode* q = &dummy;
        stack<ListNode*> stk;
        for(head != nullptr; head = head->next){
            stk.push(head);
            if(stk.size() == 2){
                while(!stk.empty()){
                    ListNode* node = stk.top();
                    stk.pop();
                    q->next = node;
                    q = q->next;
                }
            }
        }
        if(!stk.empty()){
            q->next = stk.top();
            q = q->next;
        }
        q->next = nullptr;  // 这个非常非常重要，如果不设置最后一个节点的 next 为 nullptr，链表就会出现环。
        return dummy.next;
    }
};

方法二：

使用递归:

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

解法三

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        ListNode* pre = &dummy;
        pre->next = head;

        while(pre->next && pre->next->next){
            ListNode* curr = pre->next;
            ListNode* next = curr->next;

            pre->next = next;
            curr->next = next->next;
            next->next = curr;

            pre = curr;
        }
        return dummy.next;
    }
};