我们知道单链表题型中有许多技巧, 其中有很多题都属于那种难者不会, 会者不难的题型, 满满的套路感, 下面整理了九道题目, 基本对应了七种技巧, 面试常考题型, 一起看看吧.

合并两个有序链表

题目链接: 合并两个有序链表
题目描述:

解题思路:

这道题就比较简单了, 属于单链表入门题型, 但是如果要让解法更简单, 最好定义一个虚拟头结点, 结果直接返回其next即可.

代码详解:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        ListNode* p1 = list1, *p2 = list2;

        // p1和p2均不为空时
        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
		
		// p1不为空
        if(p1)
            p->next = p1;
		// p2不为空
        if(p2)
            p->next = p2;

        return newnode->next;    
    }
};

---

分隔链表

题目链接: 分隔链表
题目描述:

解题思路:

前面一题我们是将两条有序链表合并成一条有序链表, 这一题可以将原链表分割成为两条链表.
也就是说将原链表分割成为节点值小于x的短链表和节点值不小于x的短链表即可.

注意:
如果看代码不明白的话, 最好画图去理解.

代码详解:

class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        // 定义两个虚拟头结点
        // 分成节点值小于x的短链表和节点值不小于x的短链表
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;

        // 遍历比较原链表
        while(head != nullptr)
        {
            if(head->val < x)
            {
                p1->next = head;
                p1 = p1->next;
            }
            else
            {
                p2->next = head;
                p2 = p2->next;
            }

            head = head->next;
        }

        // 将节点值不小于x的短链表的尾置空
        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};

---

合并K个有序链表

题目链接:合并K个有序链表
题目描述:

解题思路:

前面有讲到合并两个有序链表, 其实合并K个有序链表和它的解题思想很类似, 但是为了能够快速获取K个链表的最小节点, 我们需要定义一个最小堆, 将K个链表的头结点插入其中, 这样一来, 每次就可以获取K个节点的最小节点.

代码解析:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 定义一个虚拟头结点, 将所有节点尾插其后
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义一个最小堆, 将K个链表的头结点插入其中
        // 用到了C++中新语法, 不熟悉的小伙伴可以去查阅哦
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;});

        for(auto head : lists)
        {
            if(head != nullptr)
                pq.push(head);
        }

        while(!pq.empty())
        {
            // 获取堆顶节点, 即当前最小节点, 尾插到新链表后
            ListNode* pMin = pq.top();
            pq.pop();
            p->next = pMin;

            // 
            if(pMin->next != nullptr)
                pq.push(pMin->next);

            p = p->next;
        }

        return newnode->next;
    }
};

---

链表中倒数最后K个节点

题目链接: 链表中倒数最后K个节点
题目描述:

解题思路:

本题是想找到链表的最后K个节点, 前提是要找到倒数第K个节点, 如何在一次遍历的情况下找到呢?
首先定义两个指针p1和p2, 均指向链表的头结点. 一开始让p1先走k步(此时如果p1再走n-k步就走到链表的尾了), 这个时候p2从头和p1一起走, 直到p1指向nullptr为止, 此时p2在第n-k+1个节点上, 即倒数第k个位置, 大家可以画图去理解, 这里我就不画了哈哈哈哈.

代码详解:

class Solution {
public:

    ListNode* FindKthToTail(ListNode* pHead, int k) 
    {
        // write code here
        ListNode* p1 = pHead, *p2 = pHead;

        if(pHead == nullptr)
            return nullptr;

        // p1先走k步
        for(int i = 0; i < k; i++)
        {
            // 注意判断防止越界导致段错误
            if(p1)
                p1 = p1->next;
            else
                return nullptr;
        }

        // p2从头开始和p1一起走, 直至p1指向nullptr时, p2所在位置即为倒数第k个位置
        while(p1 != nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};

变形题: 删除链表的倒数第N个节点

题目链接: 删除链表的倒数第N个节点
题目描述:

解题思路:

单链表中删除某一个节点, 前提是要先找到该节点的前一个节点, 同时为了防止头删第一个节点, 我们还需要定义一个虚拟头结点, 将head节点尾插其后.

代码解析:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 定义一个虚拟头结点 - 注意单链表对虚拟头结点的运用
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 防止头删第一个节点

        // 单链表中删除某一个节点, 前提需要找到它前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);
        
        prev->next = prev->next->next;

        return newnode->next;
    }

    // 单链表中找倒数第K个节点
    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针p1和p2, p1先走k步(再走n-k步到尾), 然后p2从头开始h和p1一起走
        // 直到p1指向空, 此时p2在第n-k+1个节点的位置, 即倒数第k个节点
        ListNode* p1 = head, *p2 = head;

        if(head == nullptr)
            return nullptr;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
            else
                return nullptr;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};

---

链表的中点

题目链接: 链表的中点
题目描述:

解题思路:

利用快慢指针, 快指针一次走两步, 慢指针一次走一步, 当快指针指向末尾时, 慢指针所在的位置即是链表的中点.

代码详解:

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 快指针一次走两步, 慢指针一次走一步
        // 当快指针指向末尾时, 慢指针即是中点
        // 画图更好理解
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

---

判断链表是否有环

题目链接: 判断链表是否有环
题目描述:

解题思路:

利用快慢指针, 很简单不说了

代码详解:

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 快指针一次走两步, 慢指针一次走一步
        // 当快指针指向末尾时, 慢指针即是中点
        // 画图更好理解
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

---

环形链表II

题目链接: 环形链表II
题目描述:

解题思路:

下面是我两年前画的图…大家可以参考

代码解析:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 判断链表是否有环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        // 循环非break退出, 说明没环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // 否则有环, slow从头重新开始走
        // 二者再次相遇即为入口点
        slow = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

---

相交链表

题目链接: 相交链表
题目描述:

解题思路:

这题的解题思路就比较有意思了, 本题是求相交链表的交点, 难点在于什么, 就像上图一样, 链表A和链表B的长度很大可能不一样, 这样我们就做不到一次循环可以找到二者的交点, 那如何解决该难点呢?
我们可以定义两个指针p1和p2, 其中p1指向链表A, p2指向链表B. 一开始p1先遍历链表A然后再遍历链表B, 同理p2先遍历链表B再遍历链表A, 这样就可以保证二者遍历长度相同, 能够同时走到相交点.

代码分析:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针, p1指向链表A, p2指向链表B
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        // 为了让p1和p2遍历链表的长度一样, 采用下面的做法
        while(p1 != p2)
        {
            // p1遍历完链表A, 开始遍历链表B
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            // p2遍历完链表B, 开始遍历链表A
            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        // 交点返回即可 - 画图去理解
        return p1;
    }
};

---