《剑指offer》JZ6 从尾到头打印链表、JZ24 反转链表、JZ25 合并两个排序的链表

《剑指offer》JZ6 从尾到头打印链表、JZ24 反转链表、JZ25 合并两个排序的链表

很久没更新了，最近新开了剑指offer的坑
希望自己能刷下去。
11.26

第一题 JZ24 从尾到头打印链表

题目链接
题目大概是给了一个链表的头指针，要写一个函数把整个链表的元素获取到并且返回一个倒序排列的vector。
代码解析：

class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector ans;					//创建一个空的vector
        while(head){						//如果head指针不空
            ans.push_back(head->val);		//将当前指针的指存入vecotr尾部
            head = head->next;				//head指针指向下一个元素
        }			
        reverse(ans.begin(),ans.end());		//用reverse函数将vecotr的元素倒过来
        return ans;
    }
};

第二题 JZ24 反转链表

题目链接
题目的意思跟上面第一题一样，但是要求return的数据从vector变成了链表。
代码解析：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pre = nullptr; 
        ListNode* now = pHead;
        ListNode* nex = nullptr;  //新建三个指针分别为pre前指针，now当前指针，nex后指针
        while(now){
            nex = now->next;	//先给后指针赋值，值为当前指针的后面一个元素
            now->next = pre;    //然后就可以把当前指针向后的指针改为向前的(解题核心)
            pre = now;			//然后把前指针指向当前的指针
            now = nex;			//当前指针向后挪动一个位置
        }
        return pre;				//返回当前链表
    }
};

这大概就是朴素的多指针算法：（画了个图供大家理解）

然后运行n次，整个链表的指针就被反过来啦完美满足题目的意思。

第三题 JZ25 合并两个排序的链表

题目传送门
其实就还是链表相关的 *** 作，只是变成了两个链表合并为一个链表
比如链表1:1->3->5 链表2:2->4->6
合并为1->2->3->4->5->6
我的解题思路：

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* res = new ListNode(-1);
        ListNode* pHead=res;
        while(pHead1||pHead2){
            if(pHead1&&pHead2){
                if(pHead1->val < pHead2->val){
                    pHead->next = pHead1;
                    pHead1 = pHead1->next;
                }else{
                    pHead->next = pHead2;
                    pHead2 = pHead2->next;
                }
            }else if(pHead1){
                pHead->next = pHead1;
                pHead1 = pHead1->next;
            }else{
                pHead->next = pHead2;
                pHead2 = pHead2->next;
            }
            pHead = pHead->next;
        }
        res = res->next;
        return res;
    }
};

官方题解：

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *vhead = new ListNode(-1);
        ListNode *cur = vhead;
        while (pHead1 && pHead2) {
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next;
    }
};

看的出来总体的思路如下：（串糖葫芦）

• 新建一个指针指向一个val为-1的节点（新建一根空棍子）
• 新建另一个指针指向这个节点（新建一个手）
• 如果给出的链表中间谁的数字小就指向那个链表的首指针，那个首指针往后面指一个（手去题目给的两根糖葫芦里面拿需要的那个糖葫芦，串在空棍子上）
• 如果题目给出的某个链表的指针跑到最后面去了，那直接指向另一个串的剩余元素（有一个题目给的糖葫芦空了，直接把另外一个串在我们的结果串上）
• 返回第一个新建节点的next指针

其中，我加粗了的地方是关键，因为如果只有单个指针。处理完所有的数据了目前会指向最后一个元素，而这个元素没有前驱指针回不到链表的首地址。

其中题解的while中间的处理比我写的逻辑还是好不少，更加简洁明了，可以细心品味其中的差别。