两两交换链表中的节点

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点，在不改变节点内部值的情况下完成。

Java

思路

最重要的：要通过创建虚拟头节点！！！想清楚为什么！！！

要通过创建虚拟头节点的方式，完成对所有操作统一。

因为是两两进行交换，因此可以分为： 奇数个节点、偶数个节点。遇到奇数个节点时，我们不需要操作，直接 break 即可；遇到偶数个节点时，我们需要将节点进行交换操作；

每次移动过程中，dummy 都是会移动到下一个循环的 reverseRight ;

具体代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0, head);
        ListNode cur = dummyHead;
        while (cur != null && cur.next != null) {
            ListNode reverseLeft = cur.next;
            ListNode reverseRight = cur.next.next;
            if (reverseRight != null) {
                reverseLeft.next = reverseRight.next;
                cur.next = reverseRight;
                reverseRight.next = reverseLeft;
                cur = reverseLeft;
            } else {
                break;
            }
        }
        return dummyHead.next;
    }
}

CPP

关于指针

• cur指针:指向开始操作节点的上一节点，因此从虚拟头节点开始赋值；
• temp1：指向cur -> next，因为一开始的步骤一可以直接的连接到交换的下一节点 2，因此不需要保存 2，但是cur -> next就需要进行保存；
• temp2:指向下一对节点的第一个节点的位置，需要不断链。

定义头节点

    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;

交换过程

1. 步骤一：cur = cur -> next ->next
2. 步骤二：cur ->next ->next = temp1
3. 步骤三：temp1 -> next = temp2

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while (cur->next && cur->next->next) {
            ListNode* temp1 = cur->next;
            ListNode* temp2 = cur->next->next->next;
            cur->next = temp1->next;
            cur->next->next = temp1; // debug;
            temp1->next = temp2;
            cur = temp1;
        }
        return dummyHead->next;
    }
};

二刷代码

include <iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = head;
        ListNode* prev = dummyHead;
        while (cur && cur->next) {
            ListNode* temp1 = cur->next->next;
            prev->next = cur->next;
            cur->next->next = cur;
            cur->next = temp1;

            prev = cur;
            cur = temp1;
        }
        return dummyHead->next;
    }
};

int main()
{
    Solution s;
    ListNode *head = new ListNode(1);
    ListNode *cur = head;
    for (int i = 2; i <= 5; i++)
    {
        cur->next = new ListNode(i);
        cur = cur->next;
    }
    cur = head;
    while (cur != nullptr)
    {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
    cur = s.swapPairs(head);
    while (cur != nullptr)
    {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
    system("pause");
    return 0;
}