面试算法之链表操作集锦

超、凢脫俗 2022-11-19 04:28 213阅读 0赞

[\[+\]][Link 1]

链表操作在面试过程中也是很重要的一部分，因为它和二叉树一样都涉及到大量指针的操作，而且链表本身很灵活，很考查编程功底，所以是很值得考的地方。下面是本文所要用到链表节点的定义：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  **template** <**typename** Type>  
2.  **struct** ListNode\{  
3.      Type data;  
4.      ListNode \*next;  
5.  \};

链表的创建可以采用下面的代码，采用尾插法进行链表的创建，返回的链表没有头节点：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* Create a list, without head node 
3.   \*/  
4.  **template** <**typename** Type>  
5.  ListNode<Type> \*CreatList(Type \*data, **int** len)  
6.  \{  
7.      **if**(data == NULL || len <= 0)  
8.          **return** NULL;  
9.    
10.     ListNode<Type> \*head, \*last;  
11.   
12.     head = **new** ListNode<Type>;  
13.     last = head;  
14.   
15.     **for** (**int** i = 0; i < len; ++i)  
16.     \{  
17.         last->next = **new** ListNode<Type>;  
18.         last->next->data = data\[i\];  
19.         last = last->next;  
20.     \}  
21.   
22.     last->next = NULL;  
23.   
24.     last = head;  
25.     head = head->next;  
26.   
27.     **delete** last;  
28.   
29.     **return** head;  
30. \}

### 1.单链表的逆序打印 ###

单链表的逆序打印就是重表尾开始依次往前打印，直到表头截止，所以可以将链表逆置，然后顺序打印，但这是一种劳民伤财的做法，不仅容易出错，而且还破坏了链表的结构。这里可以采用额外的空间，来保存顺序遍历的节点，在遍历完后，就可以将该辅助空间的值逆序输出，下面是采用stack实现的代码：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* reversely print the list 
3.   \* method 1: use the stack 
4.   \*/  
5.  **template** <**typename** Type>  
6.  **void** ReversePrintList\_1(**const** ListNode<Type> \*head)  
7.  \{  
8.      **if**(head == NULL)  
9.          **return**;  
10.   
11.     stack<Type> nodeStack;  
12.     **while** (head)  
13.     \{  
14.         nodeStack.push(head->data);  
15.         head = head->next;  
16.     \}  
17.   
18.     **while**(!nodeStack.empty())  
19.     \{  
20.         cout<<nodeStack.top()<<" ";  
21.         nodeStack.pop();  
22.     \}  
23.     cout<<endl;  
24. \}

我们知道代码中，递归和栈很多时候可以相互转化，而且通过递归实现的代码会更加简洁。下面是通过递归的方式，来实现上面的功能，代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* reversely print the list 
3.   \* method 2: recursively 
4.   \*/  
5.  **template** <**typename** Type>  
6.  **void** ReversePrintList\_2(**const** ListNode<Type> \*head)  
7.  \{  
8.      **if**(head == NULL)  
9.          **return**;  
10.   
11.     ReversePrintList\_2(head->next);  
12.     cout<<head->data<<" ";  
13. \}

### 2.单链表的逆置 ###

在前面单链表的逆序打印中，有一种方法就是把单链表逆置后，再顺序打印。单链表的逆置最高效的方法，就是顺序扫描链表，然后依次逆置，代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* reverse the list 
3.   \* method 1:sequential scanning  
4.   \*/  
5.  **template** <**typename** Type>  
6.  ListNode<Type> \* ReverseList\_1(ListNode<Type> \*head)  
7.  \{  
8.      **if**(head == NULL)  
9.          **return** NULL;  
10.   
11.     ListNode<Type> \*pre = NULL;  
12.   
13.     **while** (head)  
14.     \{  
15.         ListNode<Type> \*nextNode= head->next;  
16.         head->next = pre;  
17.         pre = head;  
18.         head = nextNode;  
19.     \}  
20.   
21.     **return** pre;  
22. \}

同样可以通过递归的方式来进行逆置，递归的思想就是：将已经逆置的链表的最后一个节点返回，并把当前节点添到该节点的后面，单面如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* reverse the list 
3.   \* method 2: recursion 
4.   \*/  
5.  **template** <**typename** Type>  
6.  ListNode<Type> \* ReverseList\_2(ListNode<Type> \*head)  
7.  \{  
8.      **if**(head == NULL)  
9.          **return** NULL;  
10.   
11.     ListNode<Type> \*newHead;  
12.     SubReverseList\_2(head, newHead);  
13.   
14.     **return** newHead;  
15. \}  
16.   
17. **template** <**typename** Type>  
18. ListNode<Type> \* SubReverseList\_2(ListNode<Type> \*head, ListNode<Type> \*&newHead)  
19. \{  
20.     **if** (head->next == NULL)  
21.     \{  
22.         newHead = head;  
23.         **return** head;  
24.     \}  
25.   
26.     ListNode<Type> \*post = SubReverseList\_2(head->next, newHead);  
27.     post->next = head;  
28.     head->next = NULL;  
29.   
30.     **return** head;  
31. \}

### 3.在O(1)时间删除链表节点 ###

题目是：在一个单链表中，通过节点的指针，在O(1)时间删除该节点。该题是一个投机取巧的方法，就是将要删除的节点用下一个节点覆盖，然后删除下一个节点就可以了。但如果该节点时尾节点，O(1)的时间是不成立的。代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* delete a node from list 
3.   \*/  
4.  **template** <**typename** Type>  
5.  ListNode<Type> \* DeleteNode(ListNode<Type> \*head, ListNode<Type> \*node)  
6.  \{  
7.      **if**(head == NULL || node == NULL)  
8.          **return** head;  
9.    
10.     //only have one node  
11.     **if** (node == head && node->next == NULL)  
12.     \{  
13.         **delete** head;  
14.         **return** NULL;  
15.     \}  
16.   
17.     //node counts > 1, and delete the tail node  
18.     **if** (node->next == NULL)  
19.     \{  
20.         ListNode<Type> \*pre = head;  
21.   
22.         **while** (pre->next != node)  
23.             pre = pre->next;  
24.   
25.         **delete** node;  
26.         pre->next = NULL;  
27.   
28.         **return** head;  
29.     \}  
30.   
31.     //other node  
32.     ListNode<Type> \*delNode = node->next;  
33.     node->data = delNode->data;  
34.     node->next = delNode->next;  
35.   
36.     **delete** delNode;  
37.   
38.     **return** head;  
39. \}

### 4.链表中的倒数第k个节点 ###

求单链表的倒数第k个节点，其实是一个很简单的问题，最容易想到的是下面三种方法：

*  遍历一遍节点统计链表的长度，然后计算出倒数第k个节点在链表中顺序的位置。
 *  可以通过stack来保存链表顺序扫描的节点，然后弹出第k个节点。
 *  可以通过递归来实现。

但上面的方法都需要扫描链表超过一次或者是需要O(n)的辅助空间，如果要求只能扫描一遍链表，且是辅助空间为O(1)，那么怎么解决呢。这里有一个很巧妙的方法：用两个指针p1,p2，初始都指向第一个节点，指针p1首先向后移动k-1个节点，然后两个指针一起向后移动，直到p1指向尾节点，那么p2所指向的就是倒数第k个节点，代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* return the last k node from list, 1 =< k <= list length 
3.   \*/  
4.  **template** <**typename** Type>  
5.  **const** ListNode<Type> \* LastKNode(**const** ListNode<Type> \*head, **int** k)  
6.  \{  
7.      **if**(head == NULL || k < 1)  
8.          **return** NULL;  
9.    
10.     **const** ListNode<Type> \*ahead, \*after;  
11.     after = ahead = head;  
12.   
13.     **for** (**int** i = 0; i < k - 1; ++i)  
14.     \{  
15.         //the list length less than k  
16.         **if**(ahead->next == NULL)  
17.             **return** NULL;  
18.   
19.         ahead = ahead->next;  
20.     \}  
21.   
22.     **while** (ahead->next != NULL)  
23.     \{  
24.         ahead = ahead->next;  
25.         after = after->next;  
26.     \}  
27.   
28.     **return** after;  
29. \}

### 5.合并两个排序的链表 ###

将两个排序的单链表合并成一个链表，方法很简单，这里首先创建一个头节点，将合并的链表链接在其后面，以简化代码。代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* merge two sorted list 
3.   \*/  
4.  **template** <**typename** Type>  
5.  ListNode<Type> \* MergeTwoSortedList(ListNode<Type> \*H1, ListNode<Type> \*H2)  
6.  \{  
7.      **if** (H1 == NULL)  
8.          **return** H2;  
9.      **if** (H2 == NULL)  
10.         **return** H1;  
11.   
12.     ListNode<Type> \*head, \*last;  
13.   
14.     head = **new** ListNode<Type>;  
15.     last = head;  
16.   
17.     **while** (H1 != NULL && H2 != NULL)  
18.     \{  
19.         **if** (H1->data <= H2->data)  
20.         \{  
21.             last->next = H1;  
22.             last = H1;  
23.             H1 = H1->next;  
24.         \}   
25.         **else**  
26.         \{  
27.             last->next = H2;  
28.             last = H2;  
29.             H2 = H2->next;  
30.         \}  
31.     \}  
32.   
33.     **if** (H1 != NULL)  
34.         last->next = H1;  
35.     **else** **if** (H2 != NULL)  
36.         last->next = H2;  
37.   
38.     H1 = head->next;  
39.     **delete** head;  
40.   
41.     **return** H1;  
42. \}

### 6.求两个单链表的第一个公共结点 ###

如果两个单链表有公共结点，那么它们组成的形状一定是“**Y**”形的。求它们的第一个公共结点，可以有几种解法。

*  最暴力的解法就是从一个链表的开头，把每个结点依次与另一个链表的所有结点进行依次比较，直到找到第一个公共结点为止，这种解法那叫一个暴力，时间复杂度为O(n^2)，面试官肯定会鄙视的。
 *  采用stack辅助空间，分别将两个链表的各个结点依次入两个栈中，然后从两个栈中弹出结点，直到结点的内容不同为止，上一个结点就是所求。这种做法需要O(n)的辅助空间，估计也不是面试官最想要的。
 *  采用对齐的方法。计算两个链表的长度l1,l2，分别用两个指针p1,p2指向两个链表的头，然后将较长链表的p1(假设为p1)向后移动l2 - l1个结点，然后再同时向后移动p1,p2，直到p1 = p2。这种方法才是面试官最想要的，具体代码实现如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* Find the first common node 
3.   \*/  
4.  **template** <**typename** Type>  
5.  ListNode<Type> \* Find1stCommonNode(ListNode<Type> \*h1, ListNode<Type> \*h2)  
6.  \{  
7.      **if**(h1 == NULL || h2 == NULL)  
8.          **return** NULL;  
9.    
10.     **int** len1, len2;  
11.   
12.     len1 = GetListLength(h1);  
13.     len2 = GetListLength(h2);  
14.   
15.     **if** (len1 > len2)  
16.     \{  
17.         **for** (**int** i = 0;i < len1 - len2; ++i)  
18.             h1 = h1->next;  
19.     \}  
20.     **else**  
21.     \{  
22.         **for** (**int** i = 0;i < len2 - len1; ++i)  
23.             h2 = h2->next;  
24.     \}  
25.   
26.     **while** (h1 && h1 != h2)  
27.     \{  
28.         h1 = h1->next;  
29.         h2 = h2->next;  
30.     \}  
31.   
32.     **return** h1;  
33. \}  
34.   
35. **template** <**typename** Type>  
36. **int** GetListLength(**const** ListNode<Type> \*head)  
37. \{  
38.     **int** num = 0;  
39.   
40.     **while** (head)  
41.     \{  
42.         ++num;  
43.         head = head->next;  
44.     \}  
45.   
46.     **return** num;  
47. \}

### 7.判断两个单链表是否相交 ###

由上面6可知，相交的单链表一定是“**Y**”形的，所以如果相交，那么最后的一个节点一定相同。所以很简单，代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* judge two list crossing or not 
3.   \*/  
4.  **template** <**typename** Type>  
5.  **bool** IsCrossing(ListNode<Type> \*h1, ListNode<Type> \*h2)  
6.  \{  
7.      **if**(h1 == NULL || h2 == NULL)  
8.          **return** **false**;  
9.    
10.     **while**(h1->next != NULL)  
11.         h1 = h1->next;  
12.     **while**(h2->next != NULL)  
13.         h2 = h2->next;  
14.   
15.     **if**(h1 == h2)  
16.         **return** **true**;  
17.     **return** **false**;  
18. \}

### 8.判断单链表是否存在环 ###

判断单链表是否存在环的思想就是判断遍历的结点是否已经遍历过。那么实现上最简单的就是通过辅助空间来保存已经遍历过的结点，在每遍历一个结点时判断该结点是否已经在空间中，如果在就说明有环，否则把该结点写入辅助空间，直到找到环或访问链表结束。可以通过hashmap来保存访问的结点，查找效率是O(1)。但是需要O(n)的辅助空间。面试官想要的方法是：通过两个指针，分别从链表的头结点出发，一个每次向后移动1步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* judge the list has circle or not 
3.   \*/  
4.  **template** <**typename** Type>  
5.  **bool** HasCircle(ListNode<Type> \*head)  
6.  \{  
7.      **if**(head == NULL)  
8.          **return** **false**;  
9.    
10.     ListNode<Type> \*fast, \*slow;  
11.     fast = slow = head;  
12.   
13.     **while** (fast && fast->next != NULL)  
14.     \{  
15.         fast = fast->next->next;  
16.         slow = slow->next;  
17.   
18.         **if**(fast == slow)  
19.             **return** **true**;  
20.     \}  
21.   
22.     **return** **false**;  
23. \}

### 9.求链表的中间结点 ###

题目：求链表的中间结点，如果链表的长度为偶数，返回中间两个结点的任意一个，若为奇数，则返回中间结点。

此题的解决思路和第4题求链表的倒数第k个结点很相似。可以先求链表的长度，然后计算出中间结点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效额解法和第4题一样，通过两个指针来完成。用两个指针从链表头结点开始，一个指针每次向后移动两个结点，一个每次移动一个结点，直到移动快的那个指针移到到尾结点，那么慢的那个指针即是所求。代码如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  /\*\* 
2.   \* get the middle node of list  
3.   \*/  
4.  **template** <**typename** Type>  
5.  **const** ListNode<Type> \* ListMidNode(**const** ListNode<Type> \*head)  
6.  \{  
7.      **if**(head == NULL)  
8.          **return** NULL;  
9.    
10.     **const** ListNode<Type> \*fast, \*slow;  
11.     fast = slow = head;  
12.   
13.     **while**(fast && fast->next != NULL)  
14.     \{  
15.         fast = fast->next->next;  
16.         slow = slow->next;  
17.     \}  
18.   
19.     **return** slow;  
20. \}

如果要求在链表长度为偶数的情况下，返回中间两个结点的第一个，那么代码中的while循环判断条件可以改为如下：

**\[cpp\]**  [view plain][Link 1] [copy][Link 1]

1.  **while**(fast && fast->next != NULL && fast->next->next != NULL)

**由题4，7，8可知道，在链表的问题中，通过两个的指针来提高效率是很值得考虑的一个解决方案，所以一定要记住这种解题思路，秒杀面试官吧**。。。  
先写这么多，以后慢慢在加吧， **有新的问题大家可以提出来，一起讨论，共同进步**...<^\_^>。。。

[Link 1]: http://blog.csdn.net/anonymalias/article/details/11020477#