LeetCode链表

March 6, 2020 · 15 min read

Ban

ChangAn University

链表

链表基础

/*
        链表基础

*/

struct ListNode
{
    int value;
    ListNode *next;
};

int main()
{
    ListNode a;
    ListNode b;
    ListNode c;
    ListNode d;
    ListNode e;

    a.value = 10;
    b.value = 20;
    c.value = 30;
    d.value = 40;
    e.value = 50;

    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = NULL;

    ListNode *head = &a;

    while (head)
    {
        printf("%d", head->value);
        head = head->next;
    }

    system("pause");
    return 0;
}

206 链表逆序(Easy)

LeetCode 206. Reverse Linked List

Easy

已知链表头节点指针head，将链表逆序（不可申请额外空间）

1 -> 2 -> 3 -> 4 -> 5 -> NULL 5 -> 4 -> 3 -> 2 -> 1 -> NULL

/*
        206 链表反转
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode(int x) : val(x), next(NULL) {}
             * };

             ListNode(int x) : val(x) , next(NULL){}
             表示构造函数，传入一个x值，将x赋值给val，将NULL赋给next


*/

struct ListNode {
    int val;            //数据域
    ListNode *next;         //指针域
    ListNode(int x) : val(x), next(NULL) {}         //构造函数
};

class Solution {
public:                         //链表头节点指针
    ListNode* reverseList(ListNode* head) {
        //创建一个new_head指针，指向新链表头节点
        ListNode *new_head = NULL;
        while (head) {
            ListNode *next = head->next;//备份head->next
            head->next = new_head;//更新head-next
            new_head = head;//移动new_head

            head = next;            //遍历链表
        }
        //返回链表逆序后的头节点指针
        return new_head;
    }
};

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);

    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;

    Solution solve;

    ListNode *head = &a;

    while (head) {
        printf("%d\n", head->val);
        head = head->next;
    }

    head = solve.reverseList(&a);
    printf("after reverse : \n");

    while (head) {
        printf("%d\n", head->val);
        head = head->next;
    }



    system("pause");
    return 0;
}

JAVA

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode currentNode = head;
        ListNode newHeadNode = null;
        while (currentNode != null) {
            ListNode tempNode = currentNode.next;
            currentNode.next = newHeadNode;
            newHeadNode = currentNode;

            currentNode = tempNode;
        }

        return newHeadNode;
    }
}


class Test11{

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);

        ListNode head = null;
        head = a;
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        while(head!=null){
            System.out.println(head.val);
            head = head.next;
        }

        head = new Solution().reverseList(a);


        while(head!=null){
            System.out.println(head.val);
            head = head.next;
        }
    }
}

92 链表逆序2(Medium)

92.反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

思路

关节节点
- 逆置端头节点的前驱-> 红色节点原本红色指向蓝色，现在红色指向绿色(红->绿)
- 逆置前头节点->蓝色节点逆置前的开始节点 -> 逆置后的尾节点，逆置后尾节点指向逆置端尾节点后继（蓝->橙）
- 逆置前的尾节点->绿色节点逆置后的头节点，需要让逆置段头节点的前驱指向逆置后的头节点(红->绿)
- 逆置段尾节点的后继 -> 橙色节点逆置后，蓝色节点指向橙色节点(蓝->橙)
步骤
1. 找到逆置段头节点的前驱（红）和逆置前头节点(逆置后尾节点)（蓝） head指针向前移动m-1个位置，就找到了逆置前头节点 pre_head：记录head指针的前驱节点将逆置前头节点(蓝色)的地址存入临时变量modify_list_tail,用来操作逆置后的尾节点，让它指向逆置段尾节点的后继(橙色)
2. 逆置n-m+1个节点，记为逆置长度change_len,用简单逆置代码实现
3. 各节点相连，将逆置前头节点前驱pre_head和逆置后的头节点new_head相连，modify_list_tail与head相连
思考
1. 最终结果应该返回哪一个节点？
  将最开始的head节点记为结果节点
2. 如果m=1，需要考虑什么特殊情况？从第一个元素开始逆置 -> pre_head_pointer为NULL -> 结果为逆置前的尾节点，逆置后的头节点new_head_pointer
cpp

#include <iostream>

using namespace std;

/*
            *Definition for singly - linked list.
            * struct ListNode {
                *int val;
                *ListNode *next;
                *ListNode(int x) : val(x), next(NULL) {}
                *
            };

*/

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int change_len = n - m + 1;         //需要逆置的节点数
        ListNode *pre_head_pointer = NULL;  //初始化开始逆置的节点的前驱
        ListNode *result_pointer = head;    //最终转换后的链表头节点，非特殊情况即为head
        while (head && --m) {               //将head向前移动m-1个位置
            //1 记录head的前驱
            pre_head_pointer = head;

            head = head->next;
        }
        //将Modify_list_tail_pointer指向当前的head,即逆置后的链表尾
        ListNode *modify_list_tail_pointer = head;                      
        ListNode *new_head_pointer = NULL;

        while (head && change_len) {            //逆置change_len个节点
            ListNode *next_pointer = head->next;
            head->next = new_head_pointer;
            new_head_pointer = head;

            head = next_pointer;

            //2 每完成一个节点逆置,change_len--;
            change_len--;
        }

        //3 pre_head -> new_head   |  modify_tail_pointer -> head
        //连接逆置后的连别的链表尾与逆置段的最后一个节点
        modify_list_tail_pointer->next = head;

        if (pre_head_pointer) {             //如果pre_head_pointer不为空，说明不是从第一个节点开始逆置,m>1
            //4 将逆置链表开始的节点前驱和逆置后的头节点连接
            pre_head_pointer->next = new_head_pointer;
        }
        else {
            //5 如果pre_head为空，说明m==1从第一个节点开始逆置，结果即为逆置后的头节点
            result_pointer = new_head_pointer;
        }

        return result_pointer;
    }
};



int main() {
    Solution solve;

    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);

    ListNode *head_pointer = &a;
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;

    while (head_pointer) {
        printf("%d\n", head_pointer->val);
        head_pointer = head_pointer->next;
    }

    head_pointer = solve.reverseBetween(&a, 2, 4);

    while (head_pointer) {
        printf("%d\n", head_pointer->val);
        head_pointer = head_pointer->next;
    }

    system("pause");
    return 0;
}

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

}

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        int changeLen = n - m + 1;
        ListNode resultNode = head;
        ListNode preHeadNode = null;

        while (head != null && --m != 0) {
            preHeadNode = head;
            head = head.next;
        }
        ListNode modifyListTail = head;
        ListNode newHeadNode = null;

        while (head != null && changeLen != 0) {
            ListNode nextNode = head.next;
            head.next = newHeadNode;
            newHeadNode = head;

            head = nextNode;

            changeLen--;
        }

        modifyListTail.next = head;


        if (preHeadNode != null) {
            preHeadNode.next = newHeadNode;
        } else {
            resultNode = newHeadNode;
        }


        return resultNode;
    }


}


class Solve {

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);

        ListNode head = a;
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

        System.out.println("--------------");

        head = new Solution().reverseBetween(a, 2, 4);

        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

    }

}

160 两个链表的交点(Easy)

LeetCode 160

法1 使用set
/*
要求
1.如果两个链表没有交点,返回null
2.在求交点的过程中，不可破坏链表的结构或修改链表数据域
3.可以确保传入的链表A和链表B没有任何环
4.实现算法尽可能使时间复杂度O(n)空间复杂度O(1)

方法1 set法
1.遍历链表A,将A中节点对应指针插入set
2.遍历链表B，将B中节点对应地址指针在set中查找
发现set中的第一个节点地址，即两个链表的交点

*/

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
set<ListNode*> node_set;

while (headA) {
node_set.insert(headA);
headA = headA->next;
}

while (headB) {
if (node_set.find(headB) != node_set.end()) {
return headB;
}

headB = headB->next;
}

return NULL;
}
};

class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
List<ListNode> nodeList = new ArrayList<ListNode>();

while (headA != null) {
nodeList.add(headA);
headA = headA.next;
}

while (headB != null) {
if (nodeList.contains(headB)) {
return headB;
}

headB = headB.next;
}

return null;
}

}

class Solve {

public static void main(String[] args) {
ListNode a = new ListNode(2);
ListNode b = new ListNode(3);

a.next = b;

ListNode result = new Solution().getIntersectionNode(a, b);

System.out.println(result);

}

}

法2 - 数学计算法，空间复杂度O(1)

/*
            要求
            1.如果两个链表没有交点,返回null
            2.在求交点的过程中，不可破坏链表的结构或修改链表数据域
            3.可以确保传入的链表A和链表B没有任何环
            4.实现算法尽可能使时间复杂度O(n)空间复杂度O(1)


            法2
            1.计算两个链表长度，计算多出来的长度
            2.将长链表指针移动，移动到与短链表对齐
            3.双指针移动，找到headA==headB

*/

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

int get_list_length(ListNode *head) {
    int len = 0;
    while (head) {
        len++;
        head = head->next;
    }

    return len;
}

ListNode *forward_long_list(int long_len, int short_len, ListNode *head) {
    int delta = long_len - short_len;
    while (head && delta) {
        head = head->next;
        delta--;
    }
}

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int listA_len = get_list_length(headA);
        int listB_len = get_list_length(headB);

        if (listA_len > listB_len) {
            headA = forward_long_list(listA_len, listB_len, headA);
        }
        else {
            headB = forward_long_list(listB_len, listA_len, headB);
        }

        while (headA && headB) {
            if (headA == headB) {
                return headA;
            }

            headA = headA->next;
            headB = headB->next;
        }

    }
};

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int ALen = getListLength(headA);
        int BLen = getListLength(headB);

        if (ALen > BLen) {
            headA = getCommonStartNode(ALen, BLen, headA);
        } else {
            headB = getCommonStartNode(BLen, ALen, headB);
        }

        while (headA != null && headB != null) {
            if (headA.equals(headB)) {
                return headA;
            }

            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }

    public int getListLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }

        return len;
    }

    public ListNode getCommonStartNode(int longLen, int shortLen, ListNode head) {
        int delta = longLen - shortLen;

        while (head != null && delta != 0) {
            head = head.next;
            delta--;
        }

        return head;
    }

}

142 链表求环(Medium)

LeetCode 142

已知链表中可能存在环，若有环返回环起始节点，否则返回NULL

法一，使用Set

class Solution {
public:
    ListNode *deleteCycle(ListNode *head) {
        set<ListNode*> node_set;
        while (head) {
            if (node_set.find(head) != node_set.end()) {  //查找指针是否重复
                return head;        //重复即环起点
            }
            node_set.insert(head);      //不重复，加入Set
            head = head->next;          //遍历
        }

        return NULL;                    //从未重复，无环
    }
};


int main() {

    ListNode a(1);
    ListNode b(2);
    ListNode c(2);
    ListNode d(3);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &b;

    ListNode *result(0);

    Solution solve;

    result = solve.deleteCycle(&a);

    cout << result;


    system("pause");
    return 0;

}

法2 ，快慢指针赛跑法（经典思想）

由于链表存在环，则快指针会将慢指针套圈; 如果链表不存在环，则块指针无法套环慢指针

快指针：每次遍历走两步
慢指针：每次遍历走一步

套环则存在环->可解141题 -> 但142题要求返回环起点

如何求出环起点？

/*
            快慢指针法

*/

class Solution {
public:
    ListNode *deleteCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *meet = NULL;

        while (fast) {
            slow = slow->next;
            fast = fast->next;    //快慢指针先各走一步
            if (!fast) {               //fast等于空
                return NULL;
            }
            fast = fast->next;
    

            if (fast == slow) {
                meet = fast;
                break;
            }
        }

        if (meet == NULL) {
            return NULL;
        }

        while (head && meet) {
            if (head == meet) {
                return head;
            }

            head = head->next;
            meet = meet->next;
        }

        return NULL;
    }
};

86 链表划分(Medium)

Leecode 86 已知链表头指针head与数值x，将所有小于x的节点放在大于或等于x的节点前，且保持这些节点的原来的相对位置

设置两个临时节点：

less_head: 只要遇到小于x的节点，就用less_ptr将其插入less_head
more_head: 同理，大于x就用more_ptr插入more_head

最后将less_ptr指向域设置为more_head的下一个节点， more_ptr的指向域设置为NULL
返回less_head的next域指向的节点

class Solution {
public:
    ListNode *partition(ListNode* head, int x) {
        ListNode less_head(0);                          //定义两个临时链表头
        ListNode more_head(0);
        ListNode *less_ptr = &less_head;        //在头部定义两个指针
        ListNode *more_ptr = &more_head;

        while (head) {
            if (head->val < x) {                        //如果输入链表的头节点值小于x
                less_ptr->next = head;          //将该节点加入less_ptr指向的链表
                less_ptr = less_ptr->next;      //less_ptr往下走
            }
            else {
                more_ptr->next = head;
                more_ptr = more_ptr->next;
            }
            head = head->next;                  //输入链表往下走
        }

        less_ptr->next = more_head.next;        //将小于链表的尾巴接到大于链表的头上
        more_ptr->next = NULL;                      //将大于链表的尾巴的next域设置为NULL
        return less_head.next;                          //返回less_head指向的节点
    }
};


int main() {

    ListNode a(1);
    ListNode b(4);
    ListNode c(3);
    ListNode d(2);
    ListNode e(5);
    ListNode f(2);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;

    ListNode *result(0);

    Solution solve;

    result = solve.partition(&a, 3);

    while (result) {
        cout << result->val;
        result = result->next;
    }


    system("pause");
    return 0;

}

138 复制带随机指针的链表(hard)

LeetCode 138 Copy List With Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or NULL

Return a deep copy of the list

The Linked list is represented in the input/output as a list o n codes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node(range from 0 to n-1) where random pointer points to, or NULL if it does not point to any node

什么是深拷贝：构造生成一个全新的链表，即使将原链表毁坏，新链表可独立使用

难点：如何拷贝原链表的随机指针到新链表，如何构建新链表中的随机指针。将原链表的随机指针逻辑关系，生成在新链表中

法1： map

思路：使用Map

map实例：

#include <iostream>
#include <set>
#include <map>

using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

int main() {
    //将节点地址与整数值进行映射
    map<Node *, int> node_map;
    Node a(5);
    Node b(3);
    Node c(6);

    a.next = &b;
    b.next = &c;
    a.random = &c;
    b.random = &a;
    c.random = &c;
    
    //a的地址编号为1  b的地址编号为2  c的地址编号为3  节点地址与节点的位置进行映射
    node_map[&a] = 1;
    node_map[&b] = 2;
    node_map[&c] = 3;

    //之后，可以查看任意节点的随即指针是第几个位置
    printf("a.random id = %d\n", node_map[a.random]);
    printf("b.random id = %d\n", node_map[b.random]);
    printf("c.random id = %d\n", node_map[c.random]);

    system("pause");
    return 0;

}

思路：节点地址与节点序号对应

难点： (第几个指的是位置)

原链表某节点的random指针指向了第几个节点
新链表任意某个节点，对应为第几个节点

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node *, int> node_map;
        vector<Node *> node_vector;

        Node *ptr = head;
        int i = 0;

        while(ptr){
            node_vector.push_back(new Node(ptr->val));
            
            node_map[ptr] = i;

            ptr = ptr->next;
            i++;

        }

        node_vector.push_back(0);

        ptr = head;
        i = 0;

        while(ptr){
            node_vector[i]->next = node_vector[i + 1];
            if(ptr->random){
                int  id = node_map[ptr->random];
                node_vector[i]->random = node_vector[id];

            }

            ptr = ptr->next;
            i++;

        }

        return node_vector[0];
    }
};

法2 空间迭代法（官方题解法3）

思路查看官方题解，官方题解

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
public class Solution {
  public Node copyRandomList(Node head) {

    if (head == null) {
      return null;
    }

    // Creating a new weaved list of original and copied nodes.
    Node ptr = head;
    while (ptr != null) {

      // Cloned node
      Node newNode = new Node(ptr.val);

      // Inserting the cloned node just next to the original node.
      // If A->B->C is the original linked list,
      // Linked list after weaving cloned nodes would be A->A'->B->B'->C->C'
      newNode.next = ptr.next;
      ptr.next = newNode;
      ptr = newNode.next;
    }

    ptr = head;

    // Now link the random pointers of the new nodes created.
    // Iterate the newly created list and use the original nodes' random pointers,
    // to assign references to random pointers for cloned nodes.
    while (ptr != null) {
      ptr.next.random = (ptr.random != null) ? ptr.random.next : null;
      ptr = ptr.next.next;
    }

    // Unweave the linked list to get back the original linked list and the cloned list.
    // i.e. A->A'->B->B'->C->C' would be broken to A->B->C and A'->B'->C'
    Node ptr_old_list = head; // A->B->C
    Node ptr_new_list = head.next; // A'->B'->C'
    Node head_old = head.next;
    while (ptr_old_list != null) {
      ptr_old_list.next = ptr_old_list.next.next;
      ptr_new_list.next = (ptr_new_list.next != null) ? ptr_new_list.next.next : null;
      ptr_old_list = ptr_old_list.next;
      ptr_new_list = ptr_new_list.next;
    }
    return head_old;
  }
}

21 合并两个排序链表（Easy）

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}

};



class Solution {
public:

    ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode temp_head(0);
        ListNode *pre = &temp_head;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                pre->next = l1;
                l1 = l1->next;
            }
            else {
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;
        }

        if (l1) {       //如果l1有剩余
            pre->next = l1;
        }

        if (l2) {       //如果l2有剩余
            pre->next = l2;
        }

        return temp_head.next;
    }
};


int main() {
    Solution solve;

    // 1 2 4
    ListNode a1(1);
    ListNode a2(2);
    ListNode a3(4);
    a1.next = &a2;
    a2.next = &a3;

    // 1 3 4
    ListNode b1(1);
    ListNode b2(3);
    ListNode b3(4);
    b1.next = &b2;
    b2.next = &b3;

    // return 1 1 2 3 4 4
    ListNode* merge_list_head = solve.mergeTwoLists(&a1, &b1);

    while (merge_list_head) {
        printf("%d\t", merge_list_head->val);
        merge_list_head = merge_list_head->next;
    }

    system("pause");
    return 0;

}

23 合并多个排序链表(Hard)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

法2实现,排列法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

bool cmp(const ListNode *a, const ListNode *b)
{
    return a->val < b->val;
}

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        vector<ListNode *> node_vec;
        for (int i = 0; i < lists.size(); i++)
        {

            ListNode *head = lists[i];
            //遍历k个链表，将节点去拿不添加到node_vec
            while (head)
            {
                node_vec.push_back(head);
                head = head->next;
            }
        }

        if (node_vec.size() == 0)
        {
            return NULL;
        }
        sort(node_vec.begin(), node_vec.end(), cmp);

        for (int i = 1; i < node_vec.size(); i++)
        {
            node_vec[i - 1]->next = node_vec[i];
        }
        node_vec[node_vec.size() - 1]->next = NULL;
        return node_vec[0];
    }
};

int main()
{
    ListNode a1(3);
    ListNode a2(1);
    ListNode a3(1);

    ListNode b1(4);
    ListNode b2(2);
    ListNode b3(7);

    ListNode c1(9);
    ListNode c2(3);
    ListNode c3(5);

    a1.next = &a2;
    a2.next = &a3;

    b1.next = &b2;
    b2.next = &b3;

    c1.next = &c2;
    c2.next = &c3;

    vector<ListNode *> lists;

    lists.push_back(&a1);
    lists.push_back(&b1);
    lists.push_back(&c1);

    Solution solve;
    ListNode *result_ptr = solve.mergeKLists(lists);
    while (result_ptr)
    {
        cout << result_ptr->val << "  ";
        result_ptr = result_ptr->next;
    }

    return 0;
}

法3，分治法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
    ListNode temp_head(0);
    ListNode *pre = &temp_head;

    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            pre->next = l1;
            l1 = l1->next;
        }
        else
        {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }

    if (l1)
    { //如果l1有剩余
        pre->next = l1;
    }

    if (l2)
    { //如果l2有剩余
        pre->next = l2;
    }

    return temp_head.next;
}

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.size() == 0)
        {
            return NULL;
        }

        if (lists.size() == 1)
        {
            return lists[0];
        }

        if (lists.size() == 2)
        {
            return mergeTwoLists(lists[0], lists[1]);
        }

        int mid = lists.size() / 2; //2

        //拆分lists为两个子lists
        vector<ListNode *> sub1_lists;
        vector<ListNode *> sub2_lists;

        for (int i = 0; i < mid; i++)
        {
            sub1_lists.push_back(lists[i]);
        }

        for (int i = mid; i < lists.size(); i++)
        {
            sub2_lists.push_back(lists[i]);
        }

        ListNode *l1 = mergeKLists(sub1_lists);
        ListNode *l2 = mergeKLists(sub2_lists);

        return mergeTwoLists(l1, l2); //分治
    }
};

int main()
{
    ListNode a1(1);
    ListNode a2(3);
    ListNode a3(3);

    ListNode b1(2);
    ListNode b2(4);
    ListNode b3(7);

    ListNode c1(3);
    ListNode c2(5);
    ListNode c3(9);

    a1.next = &a2;
    a2.next = &a3;

    b1.next = &b2;
    b2.next = &b3;

    c1.next = &c2;
    c2.next = &c3;

    vector<ListNode *> lists;

    lists.push_back(&a1);
    lists.push_back(&b1);
    lists.push_back(&c1);

    Solution solve;
    ListNode *result_ptr = solve.mergeKLists(lists);
    while (result_ptr)
    {
        cout << result_ptr->val << "  ";
        result_ptr = result_ptr->next;
    }

    return 0;
}

162分钟

建议

完全自主重新编写题目解答
尽量多的通过这些题目
重新编写一边题目并提交
在纸上写代码，反复练习
完成其他leetcode链表题目

链表#

链表基础#

206 链表逆序(Easy)#

92 链表逆序2(Medium)#

160 两个链表的交点(Easy)#

142 链表求环(Medium)#

86 链表划分(Medium)#

138 复制带随机指针的链表(hard)#

法1： map#

法2 空间迭代法（官方题解 法3）#

21 合并两个排序链表（Easy）#

23 合并多个排序链表(Hard)#

建议#

链表