新冠肺炎肆虐，不如在家练练基础算法 | 链表篇

今年春节，新型冠状肺炎以迅雷不及掩耳盗铃儿响叮当之势迅速席卷了全国各地。我所在的大学正处于疫情事件的中心武汉，因此更加深刻的感受到这一场突如其来的国家公共卫生事件的严重性。

从几天前武汉市全面封城开始，全国从上到下都在推行不出门、不聚会的号召。

今年春节或许成为近几年来最为“冷清”的春节。在这个节骨眼上，也终于到了啥也不干躺在家里就能给社会做贡献的时候。也正是因为疫情的严重性，国家和各大公司相继推迟春节假期和工作开学的时间。

对个人而言，或许在为社会做贡献的同时，也可以趁机提升自己，从而可以为迎接下一次面试而做好准备。

在互联网招聘的面试环节中，手撕算法环节往往会与数据结构的考察相结合。各种经典的算法都离不开常用数据结构的支持。

本文将从最为基础的数据结构-链表出发，从leetcode中选择几道代表性的题目进行讲解，从而让同学们能够对链表的基本操作和变形算法有比较全面的了解和认识。

01

认识『链表』

链表的结构十分简单，其本身是一种线性的存储结构，通过物理地址不连续的节点相连接成链。最简单的单链表只包含一条链，并且每一个节点包括两部分内容，数据元素和下一个节点的地址。因此可通过已知节点访问它的下一个节点。

相比于数组而言，由于链表不必须按顺序存储，因而在插入的时候可以达到O(1)的复杂度，一般而言比数组的效率要高得多；但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而数组由于可以直接通过下标寻址，相应的时间复杂度仅为O(1)。

一般可通过定义结构体的方式来实现链表：

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

02

高频算法题

1. 输入一个链表，输出该链表中倒数第k个结点。

快慢指针的方法在链表相关的操作中经常使用。

通过设置快慢指针，快指针先前进k步，之后快慢指针同时前进，此时快慢指针间隔k步；当快指针到达链表尾部，此时慢指针所在节点即为倒数第k个节点。这样的方法仅通过一次遍历即可获得倒数第k个节点。

代码如下：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL||k==0)
            return NULL;
        ListNode*pTail=pListHead,*pHead=pListHead;
        for(int i=1;i<k;++i)
        {
            if(pHead->next!=NULL)
                pHead=pHead->next;
            else
                return NULL;
        }
        while(pHead->next!=NULL)
        {
            pHead=pHead->next;
            pTail=pTail->next;
        }
        return pTail;
    }
};

2. 输入一个链表，反转链表后，输出新链表的表头。

非递归方法的解题思路需要理解以下四步，具体见下图：

代码如下：

//第一种方法：非递归方法 /*
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)
            return NULL;
        
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        ListNode* head = NULL;
        
        while(cur != NULL)
        {
            if(cur->next==NULL)
                head = cur;
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
            
        }
        return head;
    }
};

//第二种方法是：递归方法 /*
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //如果链表为空或者链表中只有一个元素
        if(pHead==NULL||pHead->next==NULL) return pHead;
         
        //先反转后面的链表，走到链表的末端结点
        ListNode* pReverseNode=ReverseList(pHead->next);
         
        //再将当前节点设置为后面节点的后续节点
        pHead->next->next=pHead;
        pHead->next=NULL;
        return pReverseNode;    
}
};

3. 将两个有序链表合并为一个新的有序链表并返回。

这题可通过设置双指针的方式对链表不同节点元素进行筛选：

代码如下：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

4. 寻找两个相交链表的公共起点。

这题同样可以设置快慢指针，比较常规的方法可以先求得2个链表的长度，然后让长链表指针先前进两个链表的长度差，然后再一起前进；最后当快慢指针相遇的位置即是公共起点。

代码如下：

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        int len1 = findListLenth(pHead1);
        int len2 = findListLenth(pHead2);
        if(len1 > len2){
            pHead1 = walkStep(pHead1,len1 - len2);
        }else{
            pHead2 = walkStep(pHead2,len2 - len1);
        }
        while(pHead1 != NULL){
            if(pHead1 == pHead2) return pHead1;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return NULL;
    }
     
    int findListLenth(ListNode *pHead1){
        if(pHead1 == NULL) return 0;
        int sum = 1;
        while(pHead1 = pHead1->next) sum++;
        return sum;
    }
     
    ListNode* walkStep(ListNode *pHead1, int step){
        while(step--){
            pHead1 = pHead1->next;
        }
        return pHead1;
    }
};

5. 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

这题同样可采用快慢指针的方法来做。

快指针每次前进2步，慢指针每次前进1步。若链表有环，则快慢指针会在环内相遇。假设图中b是环的入口，a为链表起点，c为快慢指针相遇的位置。由于快慢指针的前进时间相同，则根据速度关系可得：

2(ab+bc)=ab+bc+cb+bc，则得ab=bc

所以当快慢指针相遇后，从相遇点到环入口的距离与从链表头到环入口的距离一样。通过设置一指针从链表头部前进，一指针从相遇点同时前进，两指针相遇的位置即是链表环的入口。

代码如下：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode*fast=pHead,*low=pHead;
        while(fast&&fast->next){
            fast=fast->next->next;
            low=low->next;
            if(fast==low)
                break;
        }
        if(!fast||!fast->next)
            return NULL;
        low=pHead;//low从链表头出发
        while(fast!=low){//fast从相遇点出发
            fast=fast->next;
            low=low->next;
        }
        return low;
    }
};

03

总结

链表相关的算法在面试中经常考察，其考察的重点在于对链表结构熟练的操作，包括指针的切换、节点的增删和变形等等。

上面所举的几个例子都是对链表比较基本的处理，可以从中理解到链表常用的快慢指针、遍历以及边界判断等问题。

另外，面试中出现的链表相关的高频算法题目可参考以下Leetcode题号：

Leetcode 19 删除链表的倒数第N个节点

Leetcode 21 合并两个有序链表

Leetcode 23 合并K个排序链表

Leetcode 25 K个一组翻转链表

Leetcode 86 分隔链表

Leetcode 109 有序链表转换二叉树

Leetcode 138 复制带随机指针的链表

Leetcode 141 环形链表

Leetcode 160 相交链表

Leetcode 206 反转链表

扫个关注不迷路，校招面试定不误。

推荐阅读（点击下方链接即可阅读）