文章/答案/技术大牛

发布

社区首页 >专栏 >链表算法面试问题？看我就够了！

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

五分钟学算法

发布于 2019-03-14 08:21:53

1.1K00

代码可运行

文章被收录于专栏：五分钟学算法五分钟学算法

运行总次数：0

代码可运行

1 引言

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

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

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

2.1 问题描述

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

2.2 两次遍历法

2.2.1 解题思想

（1）遍历单链表，遍历同时得出链表长度 N 。（2）再次从头遍历，访问至第 N - K 个节点为所求节点。

2.2.2 图解过程

图 1

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）由末尾开始返回，每返回一次 num 减 1 （4）当 num 为 0 时，即可找到目标节点

2.3.2 图解过程

图 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）p1 前进 K 个节点，则 p1 与 p2 相距 K 个节点。（3）p1，p2 同时前进，每次前进 1 个节点。（4）当 p1 指向到达链表末尾，由于 p1 与 p2 相距 K 个节点，则 p2 指向目标节点。

2.4.2 图解过程

图 3

图 4

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 ，而是指向了链表中的某个节点，导致链表中出现了环形结构。

链表中有环示意图：

图 5

链表的末尾节点 8 指向了链表中的节点 3，导致链表中出现了环形结构。对于链表是否是由有环的判断方法有哪些呢？

3.1.1 穷举比较法

3.1.1.1 解题思想

（1）遍历链表，记录已访问的节点。（2）将当前节点与之前以及访问过的节点比较，若有相同节点则有环。否则，不存在环。

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

3.1.2 哈希缓存法

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

3.1.2.1 解题思想

（1）首先创建一个以节点 ID 为键的 HashSe t集合，用来存储曾经遍历过的节点。（2）从头节点开始，依次遍历单链表的每一个节点。（3）每遍历到一个新节点，就用新节点和 HashSet 集合当中存储的节点作比较，如果发现 HashSet 当中存在相同节点 ID，则说明链表有环，如果 HashSet 当中不存在相同的节点 ID，就把这个新节点 ID 存入 HashSet ，之后进入下一节点，继续重复刚才的操作。

假设从链表头节点到入环点的距离是 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，并且将指针均指向链表头节点。（2）规定，slow 指针每次前进 1 个节点，fast 指针每次前进两个节点。（3）当 slow 与 fast 相等，且二者均不为空，则链表存在环。

3.1.3.2 图解过程

无环过程：

图 6

图 7

图 8

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

有环过程：

图 9

图 10

图 11

图解过程可以看出，若链表中存在环，则快慢指针必然能在环中相遇。这就好比在环形跑道中进行龟兔赛跑。由于兔子速度大于乌龟速度，则必然会出现兔子与乌龟再次相遇情况。因此，当出现快慢指针相等时，且二者不为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。则有： s = a + b; 2s = n * r + a + b; n 代表fast指针已经在环中循环的圈数。则推出： s = n * r; 意味着slow指针走过的长度为环的长度整数倍。

若链表头节点到环的末尾节点度为 L，slow 与 fast 的相遇节点距离环入口节点为 X。则有： a+X = s = n * r = (n - 1) * r + (L - a); a = (n - 1) * r + (L - a - X); 上述等式可以看出：从 slow 与 fast 相遇点出发一个指针 p1，请进 (L - a - X) 步，则此指针到达入口节点。同时指针 p2 从头结点出发，前进 a 步。当 p1 与 p2 相遇时，此时 p1 与 p2 均指向入口节点。

例如图3.1所示链表： slow 走过节点 s = 6； fast 走过节点 2s = 12；环入口节点据流头节点 a = 3；相遇点距离头节点 X = 3； L = 8； r = 6；可以得出 a = (n - 1) * r + (L - a - X)结果成立。

3.2.2 图解过程

图 12

图 13

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 图解过程

图 14

图 15

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 问题描述

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

例如：输入： 3->1->5->null 5->9->2->null，输出： 8->0->8->null

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 问题描述

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

示例：输入： 1->2->4, 1->3->4 输出： 1->1->2->3->4->4

5.2 一般方案

5.2.1 解题思想

（1）对空链表存在的情况进行处理，假如 pHead1 为空则返回 pHead2 ，pHead2 为空则返回 pHead1。（两个都为空此情况在pHead1为空已经被拦截）（2）在两个链表无空链表的情况下确定第一个结点，比较链表1和链表2的第一个结点的值，将值小的结点保存下来为合并后的第一个结点。并且把第一个结点为最小的链表向后移动一个元素。（3）继续在剩下的元素中选择小的值，连接到第一个结点后面，并不断next将值小的结点连接到第一个结点后面，直到某一个链表为空。（4）当两个链表长度不一致时，也就是比较完成后其中一个链表为空，此时需要把另外一个链表剩下的元素都连接到第一个结点的后面。

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。（2）比较两个链表第一个结点的大小，确定头结点的位置（3）头结点确定后，继续在剩下的结点中选出下一个结点去链接到第二步选出的结点后面，然后在继续重复（2 ）（3）步，直到有链表为空。

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) 时间复杂度删除该链表节点。并在删除该节点后，返回表头。

示例：给定 1->2->3->4，和节点 3，返回 1->2->4。

6.2 解题思想

在之前介绍的单链表删除节点中，最普通的方法就是遍历链表，复杂度为O(n)。如果我们把删除节点的下一个结点的值赋值给要删除的结点，然后删除这个结点，这相当于删除了需要删除的那个结点。因为我们很容易获取到删除节点的下一个节点，所以复杂度只需要O(1)。

示例单链表：1->2->3->4->NULL 若要删除节点 3 。第一步将节点3的下一个节点的值4赋值给当前节点。变成 1->2->4->4->NULL，然后将就 4 这个结点删除，就达到目的了。 1->2->4->NULL

如果删除的节点的是头节点，把头结点指向 NULL。如果删除的节点的是尾节点，那只能从头遍历到头节点的上一个结点。

6.3 图解过程

图 16

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 解法

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

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

栈！

动画 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;
    }
};