Db6536ace371944d82b147baac4c8e95
数据结构与算法——链表习题

1 引言

单链表的操作算法是笔试面试中较为常见的题目。之前写了一篇关于链表数据结构的文章,本文将着重介绍链表的应用题目。

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

2.1 问题描述

题目:输入一个单链表,输出此链表中的倒数第K个节点。(去除头结点,节点计数从1开始)

2.2 两次遍历法

2.2.1 解题思想

(1)遍历单链表,遍历同时得出链表长度N。
(2)再次从头遍历,访问至第N-k个节点为所求节点。

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(2n)。可见这种方式最为简单,也较好理解,但是效率低下。

2.3 递归法

2.3.1 解题思想

(1)定义num = k
(2)使用递归方式遍历至链表末尾。
(3)由末尾开始返回,每返回一次num减1
(4)当num为0时,即可找到目标节点

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(2n)

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

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)遍历链表,记录已访问的节点。
(2)将当前节点与之前以及访问过的节点比较,若有相同节点则有环。
否则,不存在环。

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

3.1.2 哈希缓存法

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

3.1.2.1 解题思想

(1)首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。
(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 图解过程

无环过程:

通过图解过程可以看出,若表中不存在环形,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。
则有:
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 图解过程

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;
top Created with Sketch.