链表算法面试问题看我就够了！

1 引言

单链表的操作算法是笔试面试中较为常见的题目。本文将着重介绍平时面试中常见的关于链表的应用题目。

本文大概 一万五千字 ，建议阅读时间为一个小时，请先收藏再阅读，平时也可以拿出来多看几遍。

2 输出单链表倒数第 K 个节点

2.1 问题描述

题目：输入一个单链表，输出此链表中的倒数第 K 个节点。（去除头结点，节点计数从 1 开始）。

2.2 两次遍历法

2.2.1 解题思想

（1）遍历单链表，遍历同时得出链表长度 N 。

2.2.2 图解过程

2.2.3 代码实现

/*计算链表长度*/
int listLength(ListNode* pHead){
    int count = 0;
    ListNode* pCur = pHead->next;
    if(pCur == NULL){
        printf("error");
    }
    while(pCur){
        count++;
        pCur = pCur->pNext;
    }
    return count;
}
/*查找第k个节点的值*/
ListNode* searchNodeK(ListNode* pHead, int k){
    int i = 0;
    ListNode* pCur = pHead; 
    //计算链表长度
    int len = listLength(pHead);
    if(k > len){
        printf("error");
    }
    //循环len-k+1次
    for(i=0; i < len-k+1; i++){
        pCur  = pCur->next;
    }
    return pCur;//返回倒数第K个节点
}    

采用这种遍历方式需要两次遍历链表，时间复杂度为O(n※2)。可见这种方式最为简单,也较好理解，但是效率低下。

2.3 递归法

2.3.1 解题思想

（1）定义num = k

2.3.2 图解过程

2.3.3 代码实现

int num;//定义num值
ListNode* findKthTail(ListNode* pHead, int k) {
        num = k;
        if(pHead == NULL)
            return NULL;
        //递归调用
        ListNode* pCur = findKthTail(pHead->next, k);
        if(pCur != NULL)
            return pCur;
        else{
            num--;// 递归返回一次，num值减1
            if(num == 0)
                return pHead;//返回倒数第K个节点
            return NULL;
        }
}

使用递归的方式实现仍然需要两次遍历链表，时间复杂度为O(n※2)。

2.4 双指针法

2.4.1 解题思想

（1）定义两个指针 p1 和 p2 分别指向链表头节点。

2.4.2 图解过程

2.4.3 代码实现

ListNode* findKthTail(ListNode *pHead, int K){
    if (NULL == pHead || K == 0)
        return NULL;
    //p1，p2均指向头节点
    ListNode *p1 = pHead;
    ListNode *p2 = pHead;
    //p1先出发，前进K个节点
    for (int i = 0; i < K; i++) {
        if (p1)//防止k大于链表节点的个数
            p1 = p1->_next;
        else
            return NULL;
    }
 
    while (p1)//如果p1没有到达链表结尾，则p1，p2继续遍历
    {
        p1 = p1->_next;
        p2 = p2->_next;
    }
    return p2;//当p1到达末尾时，p2正好指向倒数第K个节点
}

可以看出使用双指针法只需遍历链表一次，这种方法更为高效时间复杂度为O(n)，通常笔试题目中要考的也是这种方法。

3 链表中存在环问题

3.1 判断链表是否有环

单链表中的环是指链表末尾的节点的 next 指针不为 NULL ，而是指向了链表中的某个节点，导致链表中出现了环形结构。

链表中有环示意图：

链表的末尾节点 8 指向了链表中的节点 3，导致链表中出现了环形结构。

3.1.1 穷举比较法

3.1.1.1 解题思想

（1）遍历链表，记录已访问的节点。

这种穷举比较思想简单，但是效率过于低下，尤其是当链表节点数目较多，在进行比较时花费大量时间，时间复杂度大致在 O(n^2)。这种方法自然不是出题人的理想答案。如果笔试面试中使用这种方法，估计就要跪了，忘了这种方法吧。

3.1.2 哈希缓存法

既然在穷举遍历时，元素比较过程花费大量时间，那么有什么办法可以提高比较速度呢？

3.1.2.1 解题思想

（1）首先创建一个以节点 ID 为键的 HashSe t集合，用来存储曾经遍历过的节点。

假设从链表头节点到入环点的距离是 a ，链表的环长是 r 。而每一次 HashSet 查找元素的时间复杂度是 O(1), 所以总体的时间复杂度是 1 * ( a + r ) = a + r，可以简单理解为 O(n) 。而算法的空间复杂度还是 a + r - 1，可以简单地理解成 O(n) 。

3.1.3 快慢指针法

3.1.3.1 解题思想

（1）定义两个指针分别为 slow，fast，并且将指针均指向链表头节点。

3.1.3.2 图解过程

无环过程：

通过图解过程可以看出，若表中不存在环形，fast 与 slow 指针只能在链表末尾相遇。

有环过程：

图解过程可以看出，若链表中存在环，则快慢指针必然能在环中相遇。这就好比在环形跑道中进行龟兔赛跑。由于兔子速度大于乌龟速度，则必然会出现兔子与乌龟再次相遇情况。因此，当出现快慢指针相等时，且二者不为NULL，则表明链表存在环。

3.1.3.3 代码实现

bool isExistLoop(ListNode* pHead)  {  
    ListNode* fast;//慢指针，每次前进一个节点
    ListNode* slow;//快指针，每次前进2个节点 
    slow = fast = pHead ;  //两个指针均指向链表头节点
    //当没有到达链表结尾，则继续前进
    while (slow != NULL && fast -> next != NULL)  {  
        slow = slow -> next ; //慢指针前进一个节点
        fast = fast -> next -> next ; //快指针前进两个节点
        if (slow == fast)  //若两个指针相遇，且均不为NULL则存在环
            return true ;  
    }  
    //到达末尾仍然没有相遇，则不存在环
    return false ;  
}  

3.2 定位环入口

在 3.1 节中，已经实现了链表中是否有环的判断方法。那么，当链表中存在环，如何确定环的入口节点呢？

3.2.1 解题思想

slow 指针每次前进一个节点，故 slow 与 fast 相遇时，slow 还没有遍历完整个链表。设 slow 走过节点数为 s，fast 走过节点数为 2s。设环入口点距离头节点为 a，slow 与 fast 首次相遇点距离入口点为 b，环的长度为 r。

若链表头节点到环的末尾节点度为 L，slow 与 fast 的相遇节点距离环入口节点为 X。

例如图3.1所示链表：

3.2.2 图解过程

3.2.3 代码实现

//找到环中的相遇节点
ListNode* getMeetingNode(ListNode* pHead) // 假设为带头节点的单链表
{
    ListNode* fast;//慢指针，每次前进一个节点
    ListNode* slow;//快指针，每次前进2个节点 
    slow = fast = pHead ;  //两个指针均指向链表头节点
    //当没有到达链表结尾，则继续前进
    while (slow != NULL && fast -> next != NULL){  
        slow = slow -> next ; //慢指针前进一个节点
        fast = fast -> next -> next ; //快指针前进两个节点
        if (slow == fast)  //若两个指针相遇，且均不为NULL则存在环
            return slow;  
    }  
 
    //到达末尾仍然没有相遇，则不存在环
    return NULL ;
}
//找出环的入口节点
ListNode* getEntryNodeOfLoop(ListNode* pHead){
    ListNode* meetingNode = getMeetingNode(pHead); // 先找出环中的相遇节点
    if (meetingNode == NULL)
        return NULL;
    ListNode* p1 = meetingNode;
    ListNode* p2 = pHead;
    while (p1 != p2) // p1和p2以相同的速度向前移动，当p2指向环的入口节点时，p1已经围绕着环走了n圈又回到了入口节点。
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    //返回入口节点
    return p1;
}

3.3 计算环长度

3.3.1 解题思想

在3.1中找到了 slow 与 fast 的相遇节点，令 solw 与 fast 指针从相遇节点出发，按照之前的前进规则，当 slow 与fast 再次相遇时，slow 走过的长度正好为环的长度。

3.3.2 图解过程

3.3.3 代码实现

int getLoopLength(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while ( fast && fast->next ){
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast )//第一次相遇
            break;
    }
    //slow与fast继续前进
    slow = slow->next;
    fast = fast->next->next;
    int length = 1;       //环长度
    while ( fast != slow )//再次相遇
    {
        slow = slow->next;
        fast = fast->next->next;
        length ++;        //累加
    }
    //当slow与fast再次相遇，得到环长度
    return length;
}

4 使用链表实现大数加法

4.1 问题描述

两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。

例如：

4.2 代码实现

ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
        ListNode *ret = l1, *pre = l1;
        int up = 0;
        while (l1 != NULL && l2 != NULL) {
            //数值相加
            l1->val = l1->val + l2->val + up;
            //计算是否有进位
            up = l1->val / 10;
            //保留计算结果的个位
            l1->val %= 10;
            //记录当前节点位置
            pre = l1;
            //同时向后移位
            l1 = l1->next;
            l2 = l2->next;
        }
        //若l1到达末尾，说明l1长度小于l2
        if (l1 == NULL)
            //pre->next指向l2的当前位置
            pre->next = l2;
        //l1指针指向l2节点当前位置
        l1 = pre->next;
        //继续计算剩余节点
        while (l1 != NULL) {
            l1->val = l1->val + up;
            up = l1->val / 10;
            l1->val %= 10;
            pre = l1;
            l1 = l1->next;
        }
 
        //最高位计算有进位，则新建一个节点保留最高位
        if (up != 0) {
            ListNode *tmp = new ListNode(up);
            pre->next = tmp;
        }
        //返回计算结果链表
        return ret;
}

5 有序链表合并

5.1 问题描述

题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

5.2 一般方案

5.2.1 解题思想

（1）对空链表存在的情况进行处理，假如 pHead1 为空则返回 pHead2 ，pHead2 为空则返回 pHead1。（两个都为空此情况在pHead1为空已经被拦截）

5.2.2 代码实现

ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* pTail = NULL;//指向新链表的最后一个结点 pTail->next去连接
    ListNode* newHead = NULL;//指向合并后链表第一个结点
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL == pHead2){
        return pHead1;
    }else{
        //确定头指针
        if ( pHead1->data < pHead2->data){
            newHead = pHead1;
            pHead1 = pHead1->next;//指向链表的第二个结点
        }else{
            newHead = pHead2;
            pHead2 = pHead2->next;
        }
        pTail = newHead;//指向第一个结点
        while ( pHead1 && pHead2) {
            if ( pHead1->data <= pHead2->data ){
                pTail->next = pHead1;  
                pHead1 = pHead1->next;
            }else {
                pTail->next = pHead2;
                pHead2 = pHead2->next;
            }
            pTail = pTail->next;
 
        }
        if(NULL == pHead1){
            pTail->next = pHead2;
        }else if(NULL == pHead2){
            pTail->next = pHead1;
        }
        return newHead;
}

5.3 递归方案

5.3.1 解题思想

（1）对空链表存在的情况进行处理，假如 pHead1 为空则返回 pHead2 ，pHead2 为空则返回 pHead1。

5.3.2 代码实现

ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
    ListNode* newHead = NULL;
    if (NULL == pHead1){
        return pHead2;
    }else if(NULL ==pHead2){
        return pHead2;
    }else{
        if (pHead1->data < pHead2->data){
            newHead = pHead1;
            newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
        }else{
            newHead = pHead2;
            newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
         }
        return newHead;
    }   
}

6 删除链表中节点，要求时间复杂度为O(1)

6.1 问题描述

给定一个单链表中的表头和一个等待被删除的节点。请在 O(1) 时间复杂度删除该链表节点。并在删除该节点后，返回表头。

示例：

6.2 解题思想

在之前介绍的单链表删除节点中，最普通的方法就是遍历链表，复杂度为O(n)。

示例

如果删除的节点的是头节点，把头结点指向 NULL。

6.3 图解过程

6.4 代码实现

void deleteNode(ListNode **pHead, ListNode* pDelNode) {
        if(pDelNode == NULL)
            return;
        if(pDelNode->next != NULL){
            ListNode *pNext = pDelNode->next;
            //下一个节点值赋给待删除节点
            pDelNode->val   =  pNext->val;
            //待删除节点指针指后面第二个节点
            pDelNode->next  = pNext->next;
            //删除待删除节点的下一个节点
            delete pNext;
            pNext = NULL;
        }else if(*pHead == pDelNode)//删除的节点是头节点
         {
            delete pDelNode;
            pDelNode= NULL;
            *pHead = NULL;
        } else//删除的是尾节点
        {
            ListNode *pNode = *pHead;
            while(pNode->next != pDelNode) {
                pNode = pNode->next;
            }
            pNode->next = NULL;
            delete pDelNode;
            pDelNode= NULL;
        }
    }

7 从尾到头打印链表

7.1 问题描述

输入一个链表，按链表值从尾到头的顺序返回一个 ArrayList 。

7.2 解法

初看题目意思就是输出的时候链表尾部的元素放在前面，链表头部的元素放在后面。这不就是 先进后出，后进先出 么。

什么数据结构符合这个要求？

栈 ！

7.2.1 代码实现

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> value;
        ListNode *p=NULL;
        p=head;
        stack<int> stk;
        while(p!=NULL){
            stk.push(p->val);
            p=p->next;
        }
        while(!stk.empty()){
            value.push_back(stk.top());
            stk.pop();
        }
        return value;
    }
};

7.3 解法二

第二种方法也比较容易想到，通过链表的构造，如果将末尾的节点存储之后，剩余的链表处理方式还是不变，所以可以使用递归的形式进行处理。

7.3.1 代码实现

class Solution {
public:
    vector<int> value;
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p=NULL;
        p=head;
        if(p!=NULL){
            if(p->next!=NULL){
                printListFromTailToHead(p->next);
            }
            value.push_back(p->val);
        }
        return value;
    }
};

8 反转链表

8.1 题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

8.2 解题思路

设置三个节点pre、cur、next

• （1）每次查看cur节点是否为NULL，如果是，则结束循环，获得结果

• （2）如果cur节点不是为NULL，则先设置临时变量next为cur的下一个节点

• （3）让cur的下一个节点变成指向pre，而后pre移动cur，cur移动到next

• （4）重复（1）（2）（3）

8.3 动画演示

8.4 代码实现

8.4.1 迭代方式

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

8.4.2 递归的方式处理

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归终止条件
        if(head == NULL || head->next == NULL)
            return head;
 
        ListNode* rhead = reverseList(head->next);
        // head->next此刻指向head后面的链表的尾节点
        // head->next->next = head把head节点放在了尾部
        head->next->next = head;
        head->next = NULL;
        return rhead;
    }
};

End

今日问题：

通过本文的学习，以后遇到有关链表的面试问题我们有哪些思路去解决？

打卡格式：

打卡 X 天，答：xxx 。

欢迎关注这个程序员?

如果文章有帮助，点个“好看”吧！