Problem: 24. 两两交换链表中的节点

思路

把第一步的模拟过程的步骤记录下来
一共分为三个步骤

解题方法

创建虚拟头节点
循环什么时候结束，需要考虑问题

Q：

1. 奇数链表结束条件？
2. 偶数链表结束条件？
3. 为什么结束条件是与？

A：

• cur->next为空结束

• cur->next->next为空结束

• 如果是cur->next != NULL || cur->next->next != NULL
  则当链表为奇数链表时，cur->next != NULL也成立，不符合条件。（根据模拟过程，如果要改变1和2的位置，指针cur需要指向前一个位置，即dummy，同理，改变3和4位置，cur指向2，当3和4交换完毕，cur会指向4，再进行条件判断）
  
  注意要点
  cur->next != NULL 和cur->next->next != NULL顺序不能错，否则会出现空指针异常
  以下是链表模拟过程
  步骤一
  
  步骤2
  
  步骤3
  

Code

/**
 * Definition for singly-linked list.
 * 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 = dummyHead;

        while (cur->next != NULL && cur->next->next != NULL) // 注意是与，并且顺序不能错，不然就异常
        {
            ListNode* tmp = cur->next; // 把步骤2的内容存下
            ListNode* tmp1 = cur->next->next->next; // 把步骤3的内容存下

            cur->next = cur->next->next; // 步骤1
            cur->next->next = tmp; // 步骤2
            cur->next->next->next = tmp1; // 步骤3

            cur = cur->next->next;
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
        
    }
};