[数据结构与算法]【算法】剑指offer-反转链表&&有序链表的合并

反转链表

输入一个链表,反转链表后,输出新链表的表头

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

方法1:三指针逆置

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //链表为空 || 链表只有一个节点 ->直接返回
        if(pHead == nullptr || pHead->next == nullptr)
        {
            return pHead;
        }
		//使用三个指针,整体右移,边移动,边翻转,保证不会断链
        ListNode* prev = nullptr;
        ListNode* next = nullptr;
        while(pHead)
        {
            //prev pHead next链接
            next = pHead ->next;//保存下一个节点
            pHead ->next = prev;//重新链接
            //prev pHead往后走
            prev = pHead;
            pHead =  next;
        }
        return prev;
    }
};

方法2:使用头插法

从原链表中拿到每一个节点插入到新链表的前面,然后更换头指针指向

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //链表为空 || 链表只有一个节点 ->直接返回
        if(pHead == nullptr || pHead->next == nullptr)
        {
            return pHead;
        }
        
        ListNode* newHead = nullptr;
        while(pHead)    
        {
            ListNode* node = pHead;//把原链表的节点拿下来
            pHead = pHead->next;//原链表往后走
            
            //将node头插到新链表
            node->next = newHead;//新链表链接该节点
            newHead = node;//更换头
        }
        return newHead;
    }
};

有序链表的合并

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则.

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

方法1:一个一个节点的归并

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr && pHead2 == nullptr)
        {
            return nullptr;
        }
        if(pHead1 == nullptr) return pHead2;
        if(pHead2 == nullptr) return pHead1;
        //先选小的作为整条链表的头
        ListNode* head = pHead1->val<pHead2->val?pHead1:pHead2;
        ListNode* cur1= head==pHead1?pHead1->next:pHead2->next;
        ListNode* cur2 = cur1 == pHead1->next?pHead2:pHead1;
        ListNode* prev = head;//用于链接节点
        //合并
        while(cur1&&cur2)
        {
            if(cur1->val>cur2->val)
            {
                prev->next = cur2;
                prev = prev->next;//prev也要往后走！！！
                cur2 =cur2->next;
            }
            else
            {
                prev->next = cur1;
                prev = prev->next;//prev也要往后走！！！
                cur1 =cur1->next;
            }
        }
        //哪条链表没有结束,就让prev链表
        if(cur1)
        {
            prev->next =cur1;
        }
        if(cur2)
        {
            prev->next =cur2;
        }
        return head;
    }
};

方法2:递归归并

先对两个链表进行边界判定,一个链表为空,就返回另一个链表,如果两个链表都走到空了,返回nullptr

定义指针newhead, 比较两个链表的头节点,newhead取较小值链表的头节点, 然后小的链表头节点往后走

然后递归链接newhead->next

最后返回newhead

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1&&!pHead2)
        {
            return nullptr;
        }
        if(pHead1 == nullptr )
        {
            return pHead2;
        }
        if(pHead2 == nullptr)
        {
            return pHead1;
        }
        
        ListNode* newhead = nullptr;//找到当前两个链表中,较小的头节点
        if(pHead1->val < pHead2->val)
        {
            newhead = pHead1;
            pHead1= pHead1->next;
        }
        else
        {
            newhead = pHead2;
            pHead2= pHead2->next;
        }
        //递归归并后序节点
        newhead->next = Merge(pHead1,pHead2);
        return newhead;
    }
};