【刷题13】链表专题

一、两数相加

题目：

思路：

• 注意整数是逆序存储的，结果要按照题目的要求用链表连接起来
• 遍历l1的cur1，遍历l2的cur2，和一个整数t，用来表示进位（t等于1，要进位；t等于0，不需要进位）
• 先固定好头节点newhead，所以cur1和cur2指向的val先要运算。为什么要先固定好头节点，因为方便后面尾插
• 相加的结果为变量tmp，如果>=10，就取后面的数(%10)，并且t=1；否则直接用相加后的tmp来构造节点的值，t还是0
• 进入循环条件，只要cur1、cur2、t任意一个不为空(t不等于0)，就能进入循环，有节点，就加节点的值，没节点就用进位
• 循环中，每次的tmp要刷新为0，cur1不为空，tmp+=cur1->val，cur1往后走；cur2不为空，tmp+=cur2->val，cur2往后走；t等于1，说明有进位，tmp+=1。如果tmp>=10，tmp取后面的数，t = 1；否则还是相加后的tmp，t = 0；
• 然后构造新节点，val为tmp，尾插
• 循环后，tail->next 记得置为空（最好），返回newhead

代码：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        int t = 0;// 进位
        int tmp = cur1->val + cur2->val;
        cur1 = cur1->next;
        cur2 = cur2->next;
        if(tmp >= 10)
        {
            t = 1;
            tmp %= 10;
        }
        ListNode* newhead = new ListNode(tmp);
        ListNode* tail = newhead;
        while(cur1 || cur2 || t)
        {
            tmp = 0;
            if(cur1 != nullptr) 
            {
                tmp += cur1->val;
                cur1 = cur1->next;
            }
            if(cur2 != nullptr) 
            {
                tmp += cur2->val;
                cur2 = cur2->next;
            }
            if(t) tmp += t;

            if(tmp >= 10)
            {
                t = 1;
                tmp %= 10;
            } 
            else t = 0;

            ListNode* newnode = new ListNode(tmp);
            tail->next = newnode;
            tail = tail->next;
        }
        tail->next = nullptr;
        return newhead;
    }
};

二、两两交换链表的节点

题目：

解法一： 交换值（能过）
思路：

• 链表为空，返回空
• 链表只有一个节点，返回该链表
• 链表大于1个节点：prev指向第一个节点，cur指向第二个节点，循环为cur不为空
• 进入循环，cur和prev的节点值交换，然后prev指向cur的下一个节点，如果prev不为空，cur指向prev的下一个节点(相当于走了两步)；否则直接跳出循环
• 然后原来的链表

代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return head;
        ListNode* cur = head->next;
        ListNode* prev = head;
        while(cur)
        {
            int t = cur->val;
            cur->val = prev->val;
            prev->val = t;
            prev = cur->next;
            if(prev == nullptr) break;
            cur = prev->next;
        }
        return head;
    }
};

解法二： 交换节点
思路：

• 如果为空链表或者链表只有一个节点，直接返回head
• 定义一个哨兵位头节点，方便后续连接操作
• 定义4个指针：
  
• 注意连接顺序和可能为空的情况
• 让head重新指向修改后的tmp的next，销毁tmp，返回head

代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* tmp = new ListNode(0);
        tmp->next = head;
        ListNode* prev = tmp;
        ListNode* cur = head;
        ListNode* next = cur->next;
        ListNode* nnext = next->next;
        while(cur && next)
        {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;
            //
            prev = cur;
            cur = nnext;// 可能为空
            if(cur) next = cur->next;
            if(next) nnext = next->next;
        }
        head = tmp->next;//
        delete tmp;
        return head;
    }
};

三、重排链表

题目：

思路：

• 找到中间节点，中间节点之后逆序，然后如图先h1插入节点，再h2插入节点
• 如果链表的节点只有一个，还是原来的链表
• 找到中间节点——快慢双指针法
• 链表逆序——头插法
• 定义newhead为head，先固定第一个节点。h1为中间节点后逆序的链表，h2为head的下一个节点
• h1不为空，尾插h1的节点；h2不为slow（因为slow指向的是中间节点的位置）尾插h2的节点
• 循环结束，tail->next等于空，head=newhead，即还原head

代码：

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head->next == nullptr) head = head;
        else 
        {
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            } 
            ListNode* mid = slow;
            ListNode* h1 = nullptr;
            while(mid)
            {
                ListNode* next = mid->next;
                mid->next = h1;
                h1 = mid;
                mid = next;
            }
            ListNode* h2 = head->next;
            ListNode* newhead = head;
            ListNode* tail = newhead;
            while(h1)
            {
                tail->next = h1;
                tail = tail->next;
                h1 = h1->next;

                if(h2 != slow)
                {
                    tail->next = h2;
                    tail = tail->next;
                    h2 = h2->next;
                }
            }
            tail->next = nullptr;
            head = newhead;
        }
    }
};

四、合并k个升序链表

题目：

思路：
小堆，所有的链表的节点放入小堆，然后取顶部依次尾插（注意：要考虑链表的某个节点可能为空的情况）

代码：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int, vector<int>, greater<int>> pq;// 小堆
        ListNode* newhead =nullptr;
        ListNode* tail= nullptr;
        // k * n=500(节点数)
        for(auto &l : lists)
        {
            if(l)
            {
                ListNode* cur = l;
                while(cur)
                {
                    pq.push(cur->val);
                    cur = cur->next;
                }
            }
        }
        // log(n*k) => log(k)
        while(!pq.empty())
        {
            int t = pq.top();
            ListNode* newnode = new ListNode(t);
            if(tail == nullptr)
            {
                tail = newhead = newnode;
            }
            else 
            {
                tail->next = newnode;
                tail = tail->next;
            }
            pq.pop();
        }
        return newhead;
    }
};

五、k个一组翻转链表

题目：

思路：

• 两层循环，外面是翻转的组的个数，里面的一组的节点数（头插法）
• 先用哨兵位节点newhead固定，然后接下来每组的节点翻转后尾插到新的节点后面（刚开始是哨兵位节点，后面是上一组第一个头插的节点）
• 最后返回newhead的下一个节点，记得循环哨兵位节点

代码：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* newhead = new ListNode(0);// 哨兵位节点先固定，方便后面连接
        ListNode* tail = newhead;// 方便找尾
        int n = 0;// 节点数
        ListNode* cur = head;// 遍历链表
        while(cur)
        {
            n++;
            cur = cur->next;
        }
        n /= k;// 翻转的组的个数
        int y = k;// 为了还原原来的k值
        // 
        cur = head;// 回到第一个节点
        while(n--)// 循环组数
        {
            ListNode* tmphead = nullptr;// 临时的头指针
            // 头插法
            while(k--)// 循环要翻转(头插)的节点数
            {
                ListNode* next = cur->next;
                cur->next = tmphead;
                tmphead = cur;
                cur = next;
            }
            k = y;// 还原k
            tail->next = tmphead;// 连接翻转的后一组子链表
            // 找到尾节点，方便下次尾插新的一组子链表
            while(tail->next)
            {
                tail = tail->next;
            }
        }
        tail->next = cur;// 尾插剩余的节点
        while(tail->next)
        {
            tail = tail->next;
        }
        tail->next = nullptr;// 
        ListNode* ret = newhead->next;// 要返回的链表
        delete newhead;//
        return ret;
    }
};