第零章：单链表的六大解题套路，你都见过么？
labuladong
LeetCode
发布日期:   2021-09-09
作者:   M
文章字数:   1.7k
阅读时长:   8 分
热度:  

labuladong单链表的六大解题套路，你都见过么？

21. 合并两个有序链表

方法1：迭代

  • 逐个比较节点，不断向后移动，最后把未比较过的节点拼接到尾巴上
  • 添加一个dummy节点便于操作
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy=new ListNode(-1);
        ListNode* head=dummy;

        while( l1!=nullptr &&  l2!=nullptr){
            if ( l1->val<= l2->val){
                head->next= l1;
                 l1= l1->next;
            }else{
                head->next= l2;
                 l2= l2->next;
            }
            head=head->next;
        }
        if ( l1!=nullptr) head->next= l1;
        if ( l2!=nullptr) head->next= l2;
        return dummy->next;
    }
};
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy=ListNode(-1)
        head=dummy
        while list1 and list2:
            if list1.val<=list2.val:
                head.next=list1
                head=head.next
                list1=list1.next
            else:
                head.next=list2
                head=head.next
                list2=list2.next
        head.next=list1 if list1 else list2
        return dummy.next

方法2：递归

  • 递归结束的条件：有一个链表为空
  • 如果当前节点较小，就从当前节点的后面与另一条链表merge，然后返回当前节点对应的链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* dummy=new ListNode(-1);
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        递归结束的条件
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;        
//        融合
        if (l1->val <= l2->val){
            l1->next= mergeTwoLists(l1->next,l2);
            return l1;
        }
        else {
            l2->next= mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not list1:return list2
        if not list2:return list1
        if list1.val<list2.val:
            list1.next=self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next=self.mergeTwoLists(list1,list2.next)
            return list2

23. 合并K个升序链表

方法1：迭代地使用两两合并的算法

  • 在上一题合并2个升序链表的基础上，逐一合并所有的链表
  • 先构建一个空的x链表，不断把当前链表合并到x上，使x不断加长，最后返回x
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *head = dummy;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                head->next = l1;
                l1 = l1->next;
            } else {
                head->next = l2;
                l2 = l2->next;
            }
            head = head->next;
        }
        if (l1 != nullptr) head->next = l1;
        if (l2 != nullptr) head->next = l2;
        return dummy->next;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *x=nullptr;
        for (ListNode *cur:lists) {
            x = mergeTwoLists(x, cur); // 不断加长x链表
        }
        return x;
    }
};

方法2：优先级队列

写法1：队列中存放的是值

构建 a max heap：priority_queue <int> pq;
构建 a min heap: priority_queue<int,vector<int>,greater<int>> pq;

  • 用优先级队列（二叉堆）这种数据结构，构建一个最小堆
  • 把所有的数据通通都放进最小堆priority_queue中，然后取出来，拼接到dummy后面
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size()==0) return nullptr;
        priority_queue<int,vector<int>,greater<int>> pq;
        int sz=lists.size();
//        取出全部节点的值，放到堆中
        for (int i = 0; i < sz; ++i) {
            while(lists[i]!=nullptr){
                pq.push(lists[i]->val);
                lists[i]=lists[i]->next;
            }
        }
//        从堆中取出，然后拼接到dummy后面
        ListNode *dummy=new ListNode(-1);
        ListNode *cur=dummy;
        while(!pq.empty()){
            ListNode *tmp=new ListNode(pq.top());
            pq.pop();
            cur->next=tmp;
            cur=cur->next;
        }
        return dummy->next;
    }
};

Heap queue (or heapq) in Python


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists or len(lists) == 0:
            return None
        import heapq
        heap = []
        # 首先 for 嵌套 while 就是将所有元素都取出放入堆中
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        dummy = ListNode(None)
        cur = dummy
        # 依次将堆中的元素取出(因为是小顶堆，所以每次出来的都是目前堆中值最小的元素），然后重新构建一个列表返回
        while heap:
            cur.next=ListNode(heappop(heap))
            cur=cur.next
        return dummy.next
  • 也可以用python把所有元素逐个取出并排序，然后添加到dummy的后面
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists):
        if not lists or len(lists) == 0:
            return None
        all_vals = []
        for l in lists:
            while l:
                all_vals.append(l.val)
                l = l.next
        all_vals.sort()
        dummy = ListNode(None)
        cur = dummy
        for i in all_vals:
            cur.next=ListNode(i)
            cur=cur.next
        return dummy.next

写法3：队列中存放的是（链表的）指针

  • 重写一个比较的类，用于构建最小堆，堆中存的是链表指针
  • 假设一共有k条链表，则先找出头节点中最小的节点，加到堆中
  • 然后弹出堆顶的指针，若加进去的头结点的后面还有节点，则把这些节点也加到堆中，用于后续比较
    • 堆本来就是优先级队列，这里也有种队列的意味：出去一个堆顶指针，则加入一个堆顶对应链表的后面的一个指针（如果存在），用于后续比较。即：一次while循环中，只弹一个且只加一个指针
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class cmp1 {
public:
    bool operator()(ListNode *a, ListNode *b) {
        return a->val > b->val;
    }

};

class Solution {
public:

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size() == 0)
            return NULL;

        priority_queue < ListNode * , vector < ListNode * >, cmp1 > minHeap;
        for (ListNode *x : lists) {
            if (x) // 比较k条链表的头结点，并按递增顺序加入最小堆中
                minHeap.push(x);
        }

        ListNode *dummy = new ListNode(-1);
        ListNode *x = dummy;
        while (!minHeap.empty()) {
            ListNode *y = minHeap.top();
            minHeap.pop();
            x->next = y;
            x = x->next;
            if (y->next) {
                minHeap.push(y->next);
            }
        }
        return dummy->next;
    }
};

876. 链表的中间结点

  • 快慢指针
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow=head;
        ListNode *fast=head;
        while(fast!=nullptr && fast->next != nullptr){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

160. 相交链表

让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起

  • 若有公共交点，则最后指针指向公共交点
  • 若无公共交点，则最后指针指向NULL
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1=headA;
        ListNode *p2=headB;
        while (p1!=p2){
            p1=(p1!=nullptr?p1->next:headB);
            p2=(p2!=nullptr?p2->next:headA);
        }
        return p1;
    }
};
赏

   转载规则


《第零章：单链表的六大解题套路，你都见过么？》 由 M 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
第零章：一个方法团灭LEETCODE股票买卖问题 第零章：一个方法团灭LEETCODE股票买卖问题
labuladong一个方法团灭LEETCODE股票买卖问题用的状态机，也就是三维的dp数组（天数，是否处于持有股票的状态（用0和1表示），已经交易的次数）。根据题意不断改变状态转移方程。本文采用二维数组，把是否持有股票的状态用不同的dp
2021-09-11 LeetCode
labuladong
下一篇 
根据字符出现频率排序 根据字符出现频率排序
这类问题主要用到lambda排序 import collections m=collections.Counter(s) m=sorted(m.items(),key=lambda x: -x[1]) map<char, int> m
2021-09-08 LeetCode
LeetCode
  目录