1. 两两交换链表中的节点
题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
输入：head = [1,2,3,4]
输出：[2,1,4,3]
输入：head = []
输出：[]
输入：head = [1]
输出：[1]
思路：一开始想要不设奇偶指针，后面发现没必要，只要完成一次交换后指针p往后移两位即可。
C++:
Python：由于Python没有设置临时结点tmp，要先步骤三，防止原步骤二断线后找不到post后的结点。
笔记：注意：在画图时指针断线一定要擦掉！不然会误判！！
导致我死循环了qaq
同样，最后return也不能return head(例：图中1)，要return dummy->next(例：图中2)，否则就会丢失结点2
Python中定义新链表结点可以一步将next也初始化了
dummy = ListNode(next=head)
C++中两步
ListNode* dummy = new ListNode(0);
dummy->next = head;
C++：
// 时间复杂度 O(n)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* p = dummy;
// p->next->next为空即链表是奇数的情况，最后一个不用交换
while(p->next != nullptr && p->next->next != nullptr){
ListNode* tmp = p->next;
ListNode* tmp1 = p->next->next->next;
p->next = p->next->next; // 步骤一
p->next->next = tmp; // 步骤二
p->next->next->next = tmp1; // 步骤三
p = p->next->next;
}
return dummy->next;
}
};
Python：
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(next=head)
pre = dummy
while pre.next and pre.next.next:
p = pre.next
post = pre.next.next
p.next = post.next
post.next = p
pre.next = post
pre = pre.next.next
return dummy.next
