链表相关面试题

判断单链表是否存在环

  • 设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:
bool IsExitsLoop(List *head){
   List *slow = head, *fast = head;

   while ( fast && fast->next ){
       slow = slow->next;
       fast = fast->next->next;
       if ( slow == fast ) break;
   }

   return !(fast == NULL || fast->next == NULL);
}

寻找单链表环的入口点

  • 推演过程
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:

2s = s + nr
s= nr

设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:

list* FindLoopNode(list* head){
   list *slow = head, *fast = head;

   while ( fast && fast->next ){
       slow = slow->next;
       fast = fast->next->next;    //fast每次两步,slow每次一步
       if ( slow == fast ) break;  //当两指针相等时,判断链表中有环
   }

   if (fast == NULL || fast->next == NULL) //没有环就返回
       return NULL;

   slow = head;
   while (slow != fast){   //一个头指针,一个相遇点指针,两个第一次相等时为环入口点
        slow = slow->next;
        fast = fast->next;
   }

   return slow;
}

判断两个链表是否相交(假设两个链表均不带环)

  • 两个无环单向链表,画出来只可能是2条不相干的链表或一个”Y”字形。我们只需从第二个链表开始遍历,看是否会回到起点就可以判断出来。
  • 解法一:一个简单的做法是对第一个链表的节点地址进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果在hash表中出现,那么说明有共同的节点,时间复杂度为O(L1+L2),但是同时要附加O(L1)的存储空间。
  • 解法二:由于2个链表都没有环,我们可以把第二个链表接在第一个链表后面,如果得到的链表有环,则说明2个链表相交。这样就转换为了判断一个链表是否有环。最后,把链表再恢复原来的状态。
  • 解法三:用指针p1、p2分别指向两个链表头,不断后移;最后到达各自表尾时,若p1==p2,那么两个链表必相交,复杂度为O(L1+L2),比解法3更好
  • 总结:
    • 1.先判断带不带环
    • 2.如果都不带环,就判断尾节点是否相等
    • 3.如果都带环,判断一链表上俩指针相遇的那个节点,在不在另一条链表上。如果在,则相交,如果不在,则不相交。

判断是否带环:

struct Node{  
   int value;  
   Node * next;  
};  

//1.先判断带不带环  
//判断是否有环,返回bool,如果有环,返回环里的节点  
//思路:用两个指针,一个指针步长为1,一个指针步长为2,判断链表是否有环  
bool isCircle(Node * head, Node *& circleNode, Node *& lastNode){  
   Node * fast = head->next;  
   Node * slow = head;  
   while(fast != slow && fast && slow){  
       if(fast->next != NULL)  
           fast = fast->next;  
       if(fast->next == NULL)  
           lastNode = fast;  
       if(slow->next == NULL)  
           lastNode = slow;  
       fast = fast->next;  
       slow = slow->next;     
   }  
   if(fast == slow && fast && slow){  
       circleNode = fast;  
       return true;  
   }  
   else  
       return false;  
}

判断两个链表是否相交:

//判断带环不带环时链表是否相交  
//2.如果都不带环,就判断尾节点是否相等  
//3.如果都带环,判断一链表上俩指针相遇的那个节点,在不在另一条链表上。  
bool detect(Node * head1, Node * head2){  
   Node * circleNode1;  
   Node * circleNode2;  
   Node * lastNode1;  
   Node * lastNode2;  

   bool isCircle1 = isCircle(head1,circleNode1, lastNode1);  
   bool isCircle2 = isCircle(head2,circleNode2, lastNode2);  

   //一个有环,一个无环  
   if(isCircle1 != isCircle2){  
       return false;  
   //两个都无环,判断最后一个节点是否相等  
   }else if(!isCircle1 && !isCircle2){  
       return lastNode1 == lastNode2;  
   }  
   //两个都有环,判断环里的节点是否能到达另一个链表环里的节点  
   else{  
       Node * temp = circleNode1->next;   
       while(temp != circleNode1){  
           if(temp == circleNode2)  
               return true;  
           temp = temp->next;  
       }  
       return false;  
   }  

   return false;  
}

求链表倒数第k个结点

  • 设置两个指针p1,p2,首先p1和p2都指向head,然后p2向前走k步,这样p1和p2之间就间隔k个节点,最后p1和p2同时向前移动,直至p2走到链表末尾。
struct ListNode{
   char data;
   ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

   //求链表倒数第k个结点应该考虑k大于链表长度的case。
   ListNode* fun(ListNode *head,int k){
   assert(k >= 0);
   pone = ptwo = head;
   for( ; k > 0 && ptwo != NULL; k--)
       ptwo=ptwo->next;
   if (k > 0) return NULL;

   while(ptwo!=NULL){
       pone=pone->next;
       ptwo=ptwo->next;
   }
   return pone;
}

求链表的中间节点

  • 题目:求链表的中间节点,如果链表的长度为偶数,返回中间两个节点的任意一个,若为奇数,则返回中间节点。
  • 分析:此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度,然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表,如何解决呢?最高效的解法和第3题一样,通过两个指针来完成。用两个指针从链表头节点开始,一个指针每次向后移动两步,一个每次移动一步,直到快指针移到到尾节点,那么慢指针即是所求。

实现代码:

//求链表的中间节点
Node* theMiddleNode(Node *head){
    if(head == NULL)
        return NULL;
    Node *slow,*fast;
    slow = fast = head;
    //如果要求在链表长度为偶数的情况下,返回中间两个节点的第一个,可以用下面的循环条件
    //while(fast && fast->next != NULL && fast->next->next != NULL)  
    while(fast != NULL && fast->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

求环长

  • 求环长相对就比较容易了,就是在环的入口点设一指针和一计数器,让这一指针在环里面跑,计数器不断自增。当这一指针回到环的入口点的时候,环长就出来了。

单链表的转置

  • 即:输入一个单向链表,输出逆序反转后的链表

以下是循环与递归两种方法实现:

//单链表的转置,循环方法
Node* reverseByLoop(Node *head){
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL){
        next = head->next;

        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

//单链表的转置,递归方法
Node* reverseByRecursion(Node *head){
    //第一个条件是判断异常,第二个条件是结束判断
    if(head == NULL || head->next == NULL) 
        return head;

    Node *newHead = reverseByRecursion(head->next);

    head->next->next = head;
    head->next = NULL;

    return newHead;    //返回新链表的头指针
}

以上参考:

编程判断两个链表是否相交及求环的入口点

判断单链表是否存在环及求环入口点

面试精选:链表问题集锦

{{ message }}

{{ 'Comments are closed.' | trans }}