[数据结构与算法]leetcode 206.反转链表 24.两两交换链表中的元素

#206. 反转链表
##题目描述

##分析以及总结

• 需要将链表反转，分析一下可以得出我们需要定义三个指针变量来保存地址(用头节点直接操作的话会造成某些还未来得及操作的东西其值丢失)
• 前驱节点（当前节点的前一个） 当前节点 ， 后继节点
• 核心代码分为以下四步
• 1. p = cur->next 先将cur的后继节点给p（同时也是保证链表能遍历起来的重要一步）
• 2. cur ->next = pre 将链表进行重新链接反转
• 3. pre = cur 前驱节点后移
• 4. 当前节点后移 （不难发现只有第二步是进行反转的，剩余3步均是为了链表的遍历）

我认为的难点（出错的地方）：

• 链表的逻辑不难理解，我的问题在于边界条件以及返回值的时候出了问题，分析了好久才搞好
• 条件while（cur）即cur不为null的时候遍历 当cur是最后一个节点时 下一步就会使得cur为null，那么新的头节点就是pre了。

##具体代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *p = nullptr;
        ListNode *cur = head;
        while(cur){
            p = cur->next;
            cur->next = pre;
            pre = cur;
            cur = p;
        }
        return pre;
    }
};

#leetcode 24 两两交换链表中的元素
##题目描述

##分析

• 两两交换即每两个作为一组交换
• 采用虚拟头节点的方法会更加简单（不用再分类讨论了）
• 难点是把链表的连接与断开的逻辑搞清楚（防止还未使用是已经改变）

##个人错误点
做这个题时我无意中犯了一个错误就是我认为用临时指针保存，其之前的指针也在跟着改变（上道题说过这是错误）因此一直纠结于头节点怎么返回

##具体代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *first = new ListNode();
        first->next = head;
        ListNode *cur = first;
        while(cur->next!=nullptr && cur->next->next!=nullptr){
            ListNode *p = cur->next;    
            ListNode *q = cur->next->next->next;
            cur->next = cur->next->next;
            cur->next->next = p;
            cur->next->next->next = q;
            cur = cur->next->next; 
        }
        return first->next;
    }
};