我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

链表面试题小结

作者：我家小花儿 | 2024-08-10 20:02:16

踩

sortedmerge函数链表递增

转

链表面试题小结

某本书上面说了，链表这个东西，实际用的并不多，但是可以提供很好的考察面试者编程技巧和思维能力的素材。这里总结一下，见过的面试题和对应的候选解法。

题一、给定单链表，检测是否有环。
使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

http://ostermiller.org/find_loop_singly_linked_list.html

bool IsExistLoop(Link startNode)
{
  Link slowNode = startNode;
  Link fastNode = startNode;

  while (fastNode != NULL && fastNode->Next != NULL)
  {
    slowNode = slowNode->Next;
    fastNode = fastNode->Next->Next;

    if(slowNode == fastNode)
    {
      break;
    }
  }
  return !(fastNode == NULL || fastNode->Next == NULL);
}

这篇文章讲了很多好的坏得相关算法。

题二、给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2。假设len1>=len2，那么指针p1由head1开始向后移动len1-len2步。指针p2=head2，下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，否则说明两个链表没有交点。

   1. ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)  
   2. {  
   3.       // Get the length of two lists  
   4.       unsigned int nLength1 = ListLength(pHead1);  
   5.       unsigned int nLength2 = ListLength(pHead2);  
   6.       int nLengthDif = nLength1 - nLength2;  
   7.   
   8.       // Get the longer list  
   9.       ListNode *pListHeadLong = pHead1;  
  10.       ListNode *pListHeadShort = pHead2;  
  11.       if(nLength2 > nLength1)  
  12.       {  
  13.             pListHeadLong = pHead2;  
  14.             pListHeadShort = pHead1;  
  15.             nLengthDif = nLength2 - nLength1;  
  16.       }  
  17.    
  18.       // Move on the longer list  
  19.       for(int i = 0; i < nLengthDif; ++ i)  
  20.             pListHeadLong = pListHeadLong->m_pNext;  
  21.    
  22.       // Move on both lists  
  23.       while((pListHeadLong != NULL) && (pListHeadShort != NULL) && (pListHeadLong != pListHeadShort))  
  24.       {  
  25.             pListHeadLong = pListHeadLong->m_pNext;  
  26.             pListHeadShort = pListHeadShort->m_pNext;  
  27.       }  
  28.    
  29.       // Get the first common node in two lists  
  30.       ListNode *pFisrtCommonNode = NULL;  
  31.       if(pListHeadLong == pListHeadShort)  
  32.             pFisrtCommonNode = pListHeadLong;  
  33.    
  34.       return pFisrtCommonNode;  
  35. }  
  36.   
  37. unsigned int ListLength(ListNode* pHead)  
  38. {  
  39.       unsigned int nLength = 0;  
  40.       ListNode* pNode = pHead;  
  41.       while(pNode != NULL)  
  42.       {  
  43.             ++ nLength;  
  44.             pNode = pNode->m_pNext;  
  45.       }  
  46.       return nLength;  
  47. }

题三、给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
运用题一，我们可以检查链表中是否有环。
如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。

也可以不断开环。设重合点为p3,从p3开始遍历这个环，同时从表头开始走，检查每步是否在那个环中。这个方法大概有nlogn。

使用快慢指针，第一次相遇，表明存在循环。继续快慢指针，第二次相遇，得到的iteration步长为环的长度。分别从相遇点和第一个节点出发，都是步长为1的指针，当相遇时，得到的iteration步长为环首的位置。

题四、只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

题五、只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。

题六、给定单链表头结点，删除链表中倒数第k个结点。
使用两个节点p1,p2，p1初始化指向头结点，p2一直指向p1后第k个节点，两个结点平行向后移动直到p2到达链表尾部(NULL),然后根据p1删除对应结点。

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

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;
}

题七、链表排序

链表排序最好使用归并排序算法。堆排序、快速排序这些在数组排序时性能非常好的算法，在链表只能“顺序访问”的魔咒下无法施展能力；但是归并排序却如鱼得水，非但保持了它O(nlogn)的时间复杂度，而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n) 降到了O(1)。真是好得不得了啊，哈哈。以上程序是递推法的程序，另外值得一说的是看看那个时间复杂度，是不是有点眼熟？对！这就是分治法的时间复杂度，归并排序又是divide and conquer。

double cmp(ListNode *p ,ListNode *q)

{return (p->keyVal - q->keyVal);}

ListNode* mergeSortList(ListNode *head)

{
    ListNode *p, *q, *tail, *e;
    int nstep = 1;
    int nmerges = 0;
    int i;
    int psize, qsize;

    if (head == NULL || head->next == NULL)
    {return head;}
    while (1)
    {   p = head;
    tail = NULL;
    nmerges = 0;
    while (p)
    {   nmerges++; q = p; psize = 0;
    for (i = 0; i < nstep; i++){
        psize++;
        q = q->next;
        if (q == NULL)break;
    }
    qsize = nstep;
    while (psize >0 || (qsize >0 && q))
    {
        if (psize == 0 ){e = q; q = q->next; qsize--;}

        elseif (q == NULL || qsize == 0){e = p; p = p->next; psize--;}

        elseif (cmp(p,q) <= 0){e = p; p = p->next; psize--;}

        else{e = q; q = q->next; qsize--;}

        if (tail != NULL){tail->next = e;}

        else{head = e;}

        tail = e;

    }
    p = q;

    }
    tail->next = NULL;
    if (nmerges <= 1){return head;}
    else{nstep <<= 1;}
    }
}

题八、倒转单链表

利用三个连续指针cur、fw1、fw2，从头(设定为slink)开始指向三个节点，然后进行反转操作，循环进行：

//最开始的状态
cur = slink;
fw1 = slink->next;
fw2 = fw1->next;
slink->next = NULL;

//反转一次
fw1->next = cur;
cur = fw1;
fw1 = fw2;
fw2 = fw2->next;

完整的代码请参考：

struct mynode{ int data; struct mynode *next; }; struct mynode *single_link_reverse(struct mynode *slink) { struct mynode *cur; struct mynode *fw1; struct mynode *fw2; /* zero or one node*/ if (NULL == slink || NULL == slink->next) return slink; cur = slink; fw1 = slink->next; fw2 = fw1->next; slink->next = NULL; /*two nodes*/ if (NULL == fw2) { fw1->next = cur; return fw1; } /*three+ nodes*/ while (NULL != fw2) { fw1->next = cur; cur = fw1; fw1 = fw2; fw2 = fw2->next; } /*now fw1 is the last node*/ fw1->next = cur; return fw1; }

题九、两个有序链表的合并

写一个函数SortedMerge函数，该函数有两个参数，都是递增的链表，函数的功能就是合并这两个递增的链表为一个递增的链表，SortedMerge的返回值是新的链表。新链表由前两个链表按元素递增顺序合并而成，也就是说它不会创建新的元素。

比如：这里有两个链表，分别是

list1: 5->10->15

list2: 2->3->20

SortedMerge函数返回一个指向新链表的指针，新链表应该是如下这样的：2->3->5->10->15->20

程序需要考虑如下情况：两个链表（函数参数）都有可能为空，也可能其中一个链表已经遍历完了，另一个链表还有很多元素。

方法1（虚拟节点）

这种方法用一个虚拟节点（dummy node）作为结果链表的起始节点，为了方便在链表尾部插入节点，还需要用一个尾指针指向链表的尾节点。

初始时，结果链表为空的时候，尾指针指向的是虚拟节点。因为虚拟节点是一个在栈上分配的临时变量，所以对它的操作都是非常高效的。在循环迭代中，每次从a 或b中取一个节点插入到结果链表的尾部，循环结束时，虚拟节点的next域就是结果链表的地址，也就是我们期望的返回值。

[cpp] view plain copy print ?

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/*Link list node*/
struct node
{
int data;
struct node* next;
};
/*Function to insert a node at the begining of the linked list*/
void push(struct node** head_ref, int new_data)
{
/* allocate node*/
struct node* new_node = (struct node*)malloc(sizeof(struct node));
/* put in the data*/
new_node->data = new_data;
/*link the old list off the new node*/
new_node->next = (*head_ref);
/*move the head to point to the new node*/
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct node* node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
/*pull off the front node of the source and put it in dest*/
/* MoveNode() function takes the node from the front of the source, and move it to
the front of the dest.
It is an error to call this with the source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
After calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3}
*/
void MoveNode(struct node** destRef, struct node** sourceRef)
{
/* the front source node */
struct node* newNode = *sourceRef;
assert(newNode != NULL);
/*Advance the source pointer */
*sourceRef = newNode->next;
/* Link th eold dest off the new node */
newNode->next = *destRef;
/*Move dest to point to the new node */
*destRef = newNode;
}
/*Takes two lists sorted in creasing order, and splices their nodes together to
make ont big sorted list which is returned. */
struct node* SortedMerge(struct node* a, struct node* b)
{
/* a dummy first node to hang the result on */
struct node dummy;
/* tail points to the last result node */
struct node* tail = &dummy;
/*so tail->next is the places to add new nodes to the result*/
dummy.next = NULL;
while(1)
{
if(a == NULL)
{
tail->next = b;
break;
}
else if(b == NULL)
{
tail->next = a;
break;
}
if(a->data <= b->data)
{
MoveNode(&(tail->next), &a);
}
else
{
MoveNode(&(tail->next), &b);
}
tail = tail->next;
}
return (dummy.next);
}
/*Drier program to test above functions */
int main(int argc, char* argv[])
{
/*start with the empty list */
struct node* res = NULL;
struct node* a = NULL;
struct node* b = NULL;
/*Let us create two sorted linked lists to test the functions
Created lists shall be a:5->10->15, b:2->3->20 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
res = SortedMerge(a, b);
printf("\nMerged Linked List is:\n");
printList(res);
return 0;
}


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
/*Link list node*/
struct node
{
	int data;
	struct node* next;
};
 
/*Function to insert a node at the begining of the linked list*/
void push(struct node** head_ref, int new_data)
{
	/* allocate node*/
	struct node* new_node = (struct node*)malloc(sizeof(struct node));
	
	/* put in the data*/
	new_node->data = new_data;
	
	/*link the old list off the new node*/
	new_node->next = (*head_ref);
 
	/*move the head to point to the new node*/
	(*head_ref) = new_node;
}
 
/* Function to print nodes in a given linked list */
void printList(struct node* node)
{
	while(node != NULL)
	{
		printf("%d ", node->data);
		node = node->next;
	}
	printf("\n");
}
 
/*pull off the front node of the source and put it in dest*/
/* MoveNode() function takes the node from the front of the source, and move it to 
the front of the dest.
It is an error to call this with the source list empty.
	Before calling MoveNode():
	source == {1, 2, 3}
	dest == {1, 2, 3}
	
	After calling MoveNode():
	source == {2, 3}
	dest == {1, 1, 2, 3}
*/
 
void MoveNode(struct node** destRef, struct node** sourceRef)
{
	/* the front source node */
	struct node* newNode = *sourceRef;
	assert(newNode != NULL);
	
	/*Advance the source pointer */
	*sourceRef = newNode->next;
	
	/* Link th eold dest off the new node */
	newNode->next = *destRef;
 
	/*Move dest to point to the new node */
	*destRef = newNode;
}
 
/*Takes two lists sorted in creasing order, and splices their nodes together to 
make ont big sorted list which is returned. */
struct node* SortedMerge(struct node* a, struct node* b)
{
	/* a dummy first node to hang the result on */
	struct node dummy;
	
	/* tail points to the last result node */
	struct node* tail = &dummy;
	
	/*so tail->next is the places to add new nodes to the result*/
	dummy.next = NULL;
	while(1)
	{
		if(a == NULL)
		{
			tail->next = b;
			break;
		}
		else if(b == NULL)
		{
			tail->next = a;
			break;
		}
 
		if(a->data <= b->data)
		{
			MoveNode(&(tail->next), &a);
		}
		else
		{
			MoveNode(&(tail->next), &b);
		}
		tail = tail->next;
	}	
	return (dummy.next);
}
/*Drier program to test above functions */
int main(int argc, char* argv[])
{
 
	/*start with the empty list */
	struct node* res = NULL;
	struct node* a = NULL;
	struct node* b = NULL;
 
	/*Let us create two sorted linked lists to test the functions 
	Created lists shall be a:5->10->15, b:2->3->20 */
 
	push(&a, 15);
	push(&a, 10);
	push(&a, 5);
 
	push(&b, 20);
	push(&b, 3);
	push(&b, 2);
 
	res = SortedMerge(a, b);
	printf("\nMerged Linked List is:\n");
	printList(res);
	return 0;
}

方法2（局部引用）

这种方法与上一种方法非常相似。这种方法避免使用虚拟节点(dummy node)，而是使用一个指向指针的指针，struct node** lastPtrRef，这个指针指向结果链表的最后一个节点。在这个方法中，所有由虚拟节点完成的工作都有lastPtrRef完成。

[cpp] view plain copy print ?

/* method2 Using local References */
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/*point to the last result pointer */
struct node** lastPtrRef = &result;
while(1)
{
if(a == NULL)
{
*lastPtrRef = b;
break;
}
else if(b == NULL)
{
*lastPtrRef = a;
break;
}
if(a->data <= b->data)
{
MoveNode(lastPtrRef, &a);
}
else
{
MoveNode(lastPtrRef, &b);
}
/*tricky:advance to point to the next ".next" field */
lastPtrRef = &((*lastPtrRef)->next);
}
return (result);
}


/* method2 Using local References */
struct node* SortedMerge(struct node* a, struct node* b)
{
	struct node* result = NULL;
 
	/*point to the last result pointer */
	struct node** lastPtrRef = &result;
 
	while(1)
	{
		if(a == NULL)
		{
			*lastPtrRef = b;
			break;
		}
		else if(b == NULL)
		{
			*lastPtrRef = a;
			break;
		}
		if(a->data <= b->data)
		{
			MoveNode(lastPtrRef, &a);
		}
		else
		{
			MoveNode(lastPtrRef, &b);
		}
		/*tricky:advance to point to the next ".next" field */
		lastPtrRef = &((*lastPtrRef)->next);
	}
	return (result);
}

方法3（递归）

合并操作是非常适合用递归来完成的一类操作，递归实现将会比迭代实现更加清晰且易于理解。尽管如此，你可能也不愿意使用递归来实现这个操作，因为递归方法所使用的栈空间与链表的长度成正比。

[cpp] view plain copy print ?

/*Using Recursion*/
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/*Base cases*/
if(a == NULL)
return (b);
else if(b == NULL)
return (a);
/*Pick either a or b, and recur */
if(a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return (result);
}

题十、找出链表的中间元素


单链表的一个比较大的特点用一句广告语来说就是“不走回头路”，不能实现随机存取
（random access）。如果我们想要找一个数组a的中间元素，直接a[len/2]就可以了，
但是链表不行，因为只有a[len/2 - 1] 知道a[len/2]在哪儿，其他人不知道。因此，
如果按照数组的做法依样画葫芦，要找到链表的中点，我们需要做两步（1）知道链表有多长（2）
从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n（n为链表的长度）的时间复杂度了。
有没有更好的办法呢？有的。想法很简单：两个人赛跑，如果A的速度是B的两倍的话，
当A到终点的时候，B应该刚到中点。这只需要遍历一遍链表就行了，还不用计算链表的长度。
 
其他参考：

程序员编程艺术：第九章、闲话链表追赶问题

微软面试100题系列：一道合并链表问题的解答[第42题]

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/960124