链表面试题

程序员文章站 2022-05-06 11:04:05

...

链表面试题

基础
1.比较顺序表和链表的优缺点，说说它们分别在什么场景下使用？
1.从尾到头打印单链表
2.删除一个无头单链表的非尾节点
3.在无头单链表的一个节点前插入一个节点
4.单链表实现约瑟夫环
5.逆置/反转单链表
6.单链表排序（冒泡排序&快速排序）
7.合并两个有序链表,合并后依然有序
8.查找单链表的中间节点，要求只能遍历一次链表
9.查找单链表的倒数第k个节点，要求只能遍历一次链表

进阶
1.判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度。
2.判断两个链表是否相交，若相交，求交点。（假设链表不带环）
3.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】
4.复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

基础：
1.从尾到头打印单链表
思路：新开辟一个数组，每遍历到一个结点，就把它插入到当前元素之前，再把数组内容输出。

struct ListNode {
      int val;
      struct ListNode *next;
       ListNode(int x)
             : val(x)
             , next(NULL)
        {}
};

class Solution {
public:
     vector<int> printListFromTailToHead(ListNode* head) {
          vector<int> res;
          if (head != NULL)
          {
              res.insert(res.begin(), head->val);
              while (head->next != NULL)
              {
                   res.insert(res.begin(), head->next->val);
                   head = head->next;
              }
          }
          return res;
     }
};

2.删除一个无头单链表的非尾节点
思路：替换法删除，我们要删除node位置的结点，必须知道node之前的那个节点，但是没法知道，所以我们转变思维，我们可以找到node之后的那个节点，把之后的那个节点替换到node的位置，删除node之后的那个节点即可。

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

class Solution {
public:
     void deleteNode(ListNode* node)
     {
          if (node == NULL)
                return;
          node->val = node->next->val;          
          ListNode* delNode = node->next;          
          node->next = delNode->next;          
     }
};

3.在无头单链表的一个非有头节点前插入一个节点
和上一题的思路一样

void InsertNode(ListNode* pos, int x)
{
     assert(pos);
     ListNode* next = pos->next;
     ListNode* tmp = new ListNode(pos->val);//交换pos和tmp的数据
     pos->val = x;
     pos->next = tmp;
     tmp->next = next;
}

4.单链表实现约瑟夫环
约瑟夫环

struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x)
          : val(x)
          , next(NULL)
     {}
};

ListNode* Joesphus(ListNode* pos, int k)
{
     assert(pos);
     ListNode* man = pos;
     ListNode* tmp = NULL;
     while (man->next != man)
     {
          int count = k;
          while (--k)//man指向的位置刚好为要自杀的人
          {
              man = man->next;
          }
          tmp = man->next;//替换法
          man->val = tmp->val;
          man->next = tmp->next;
          delete tmp;
     }
     return man;
}

5、逆置/反转单链表
链表面试题

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

//时间复杂度：O(N)
//空间复杂度：O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
         ListNode* pre = NULL;
         ListNode* cur = head;

         while (cur)
         {
             ListNode* next = cur->next;
             cur->next = pre;
             pre = cur;
             cur = next;
         }
         return pre;
    }
};

6.单链表排序（冒泡排序）

void BubbleSortList(ListNode* head)
{
     if (head == NULL || head->next == NULL)
          return;
     ListNode* cur = head, *tail = NULL, *next = cur->next;
     while (tail != head->next)
     {
          int flag = 0;
          while (next != tail)
          {
              if (cur->val > next->val)
              {
                   int tmp = cur->val;
                   cur->val = next->val;
                   next->val = tmp;
                   flag = 1;
              }
              cur = cur->next;
              next = next->next;
          }
          if (flag == 0)
              break;
          tail = cur;
     }
}

7.合并两个有序链表,合并后依然有序

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

class Solution {
public:
     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
          if (l1 == NULL)
              return l2;
          if (l2 == NULL)
              return l1;
          ListNode *newList = NULL;
          if (l1->val <= l2->val)
          {
              newList = l1;
              newList->next = mergeTwoLists(l1->next, l2);
          }
          else
          {
              newList = l2;
              newList->next = mergeTwoLists(l1, l2->next);
          }
          return newList;
     }
};

8.查找单链表的中间节点，要求只能遍历一次链表
思路：定义一个快指针和慢指针，快指针每次走两步，慢指针每次走一步（奇数个时返回中间节点，偶数个时返回偶数个中间的前一个所以要判断fast->next->next）

struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x)
          : val(x)
          , next(NULL)
     {}
};

class Soultion{
public:
     ListNode* FindMidNode(ListNode* head)
     {
          ListNode* slow = head, *fast = head;
          while (fast && fast->next && fast->next->next)
          {
              slow = slow->next;
              fast = fast->next->next;
          }
          return slow;
     }
};

9.查找单链表的倒数第k个节点，要求只能遍历一次链表
思路：也是快慢指针的思想，让快指针先走k-1步，然后让两个指针同时走，最后慢指针就指向了倒数第K个节点的位置。

struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x)
          : val(x)
          , next(NULL)
     {}
};

class Solution {
public:
     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
          if (pListHead == NULL || k <= 0)
              return NULL;

          ListNode *slow = pListHead;
          ListNode *fast = pListHead;

          for (int i = 0; i < k - 1; i++)
          {
              if (fast->next == NULL)
                return NULL;
              fast = fast->next;
          }
          while (fast->next)
          {
              fast = fast->next;
              slow = slow->next;
          }
          return slow;
     }
};

进阶：
1.判断单链表是否带环？若带环，求环的长度？求环的入口点？

思路：判断链表是否带环，一个快指针，一个慢指针，慢指针走一步，快指针走两步，如果进环了，快指针一定会在环内追上慢指针，俩指针就会相遇。
但是，慢指针一次走一步，快指针一次走三或三步以上步，就有特殊情况，使得两者不能相遇。例如：只有两个节点的情况。

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

class Solution {
public:
     ListNode* hasCycle(ListNode *head) {
          ListNode * slow = head, *fast = head;
          while (fast && fast->next)
          {
              slow = slow->next;
              fast = fast->next->next;
              if (slow == fast)
                   return fast;
          }
          return NULL;
     }
};

2.求环长度
思路：在判断是否有环时，可以求出相遇点。然后定义一个指针，从相遇点开始走一圈，下次走到相遇点时就为环的长度。

int GetCycleLen(ListNode* meetNode)
{
     ListNode* slow = meetNode;;
     int count = 0;
     assert(slow);
     slow = slow->next;
     count++;
     while (slow != meetNode)
     {
          count++;
          slow = slow->next;
     }
     return count;
}

3.求入口点
链表面试题

ListNode* GetEntry(ListNode* head, ListNode* meetNode)
{
     ListNode* start = head;
     ListNode* meet = meetNode;
     assert(start && meet);
     while (start != meet)
     {
          start = start->next;
          meet = meet->next;
          if (start == meet)
          {
              return meet;
          }
     }
     return NULL;
}

2.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

两个链表相交，只有下面的这种可能。
链表面试题
思路：首先获得两个链表的长度，就可以知道哪个链表长，哪个链表短，以及长链表比短链表多出几个结点，然后让长的链表先走几步，接着两个同时走，找到的第一个相同点就是它们相交的结点。

struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x)
          :val(x)
          ,next(NULL)
     {}
};

class Solution {
public:
     ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
          if (phead1 == NULL ||phead2 == NULL)
              return NULL;
          //得到两个链表的长度
          unsigned int length1 = GetListLength(pHead1);
          unsigned int length2 = GetListLength(pHead2);

          int length = length1 - length2;

          ListNode* pListHeadLong = pHead1;
          ListNode* pListHeadshort = pHead2;
          if (length2 > length1)
          {
              pListHeadLong = pHead2;
              pListHeadshort = pHead1;
              length = length2 - length1;
          }

          //先在长链表上走几步，然后同时在两个链表上遍历
          for (int i = 0; i < length; i++)
              pListHeadLong = pListHeadLong->next;


          while (pListHeadLong != NULL && pListHeadshort != NULL && pListHeadLong != pListHeadshort)
          {
              pListHeadLong = pListHeadLong->next;
              pListHeadshort = pListHeadshort->next;
          }


          //得到了第一个公共结点
          ListNode* FirstCommonNode = pListHeadshort;
          return FirstCommonNode;
     }


     int GetListLength(ListNode* pHead)
     {
          unsigned int length = 0;
          ListNode* Node = pHead;
          while (Node != NULL)
          {
              ++length;
              Node = Node->next;
          }
          return length;
     }
};

3.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）

思路：
链表面试题
4.复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。

思路：
①拷贝出结点
②置Random指针
③再拆分成两个链表

struct RandomListNode {
     int label;
     struct RandomListNode *next, *random;
     RandomListNode(int x)
          : label(x)
          , next(NULL)
          , random(NULL)
     {}
};

class Solution {
public:
     RandomListNode* Clone(RandomListNode* pHead)
     {
          //1.插入拷贝节点
          RandomListNode* cur = pHead;
          while (cur)
          {
              RandomListNode* next = cur->next;
              RandomListNode* copy = BuyNode(cur->label);
              copy->next = next;
              cur->next = copy;
              cur = next;
          }
          //2.置Random
          cur = pHead;
          while (cur)
          {
              RandomListNode* copy = cur->next;
              if (cur->random)
              {
                   copy->random = cur->random->next;
              }
              cur = copy->next;
          }
          //3.拆解成两个链表
          RandomListNode* copyHead = NULL;
          RandomListNode* copyTail = NULL;
          cur = pHead;
          while (cur)
          {
              RandomListNode* copy = cur->next;
              RandomListNode* next = copy->next;
              cur->next = next;
              if (copyHead == NULL)
              {
                   copyHead = copyTail = copy;
              }
              else
              {
                   copyTail->next = copy;
                   copyTail = copy;
              }
              cur = next;
          }
          return copyHead;
     }
     RandomListNode* BuyNode(int data)
     {
          RandomListNode* node = new RandomListNode(data);
          node->label = data;
          node->next = NULL;
          node->random = NULL;
          return node;
     }
};

相关标签：复杂链表的复制倒数第K个节点

上一篇： Java GUI 实现登录注册界面

下一篇：单链表常见面试题

链表面试题

链表面试题

PHP的关于变量和日期处理的一些面试题目整理

合并两个有序链表（C++语言开发）

从一道没人能答对的面试题聊聊Java的值传递

《剑指offer》面试题6 重建二叉树

PHP面试题2019年百度工程师面试题和答案解析

SQL优化|Java面试题

python无序链表删除重复项的方法

5个实用的shell脚本面试题和答案

shell实现FizzBuzzWhizz问题示例(拉勾网面试题)

javascript实现上传图片前的预览（TX的面试题）