链表面试题(一):反转链表的算法实现

时间:2022-11-03 09:40:48

关于链表的考察

  链表是面试里面经常涉及到的考点,因为链表的结构相比于Hashmap、Hashtable、Concurrenthashmap或者图等数据结构简单许多,对于后者更多面试的侧重点在于其底层实现。比如Hashmap中Entry<k,v>等操作、如何扩容、容量的设定等。链表的考察更侧重于代码的书写和思路的形成。虽然说,链表的结构简单,但是涉及到指针的操作,容易引申出一些挑战性的考题,其中也牵涉到诸多小的细节的考虑,更能看出代码书写的能力和功底。

面试题:反转链表

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

  下面给出了链表结点的定义:

1 struct ListNode {
2 int val;
3 struct ListNode *next;
4 ListNode(int x) :
5 val(x), next(NULL) {
6 }
7 };

分析:

  链表前后元素的关联就是通过指针实现的,每个链表都有一个next指针指向下一个结点,末尾的节点的next域则置NULL;

  反转链表就是要求修改指针的指向。下面的图就是反转前和反转后的效果。

反转前:

链表面试题(一):反转链表的算法实现

反转后:

链表面试题(一):反转链表的算法实现

下面来谈谈如何对链表进行反转。

链表面试题(一):反转链表的算法实现

  假设我们现在正在对结点v进行反转操作,即原来结点u的next域指向v(图中已经调整完毕,现在指向前一个结点),v的next域指向w。现在要做的是将v的next域指向u。从图中我们可以看出,当把v的next指针指向u的同时,原先指向的w就已经无法被正常的访问到了,为了避免“断链”,我们必须在指针更改指向之前,保存修改结点的下一结点。同时我们也必须存储上一个结点,因为next域即将修改指向该结点。因此定义三个指针,分别指向当前遍历的结点,前一个结点和后一个结点。

算法实现如下:

 1 ListNode* ReverseList(ListNode* pHead)
2 {
3 ListNode* pReversedHead = NULL;
4 ListNode* pNode = pHead;
5 ListNode* pPrev = NULL;
6 while(pNode != NULL)
7 {
8 ListNode* pNext = pNode->m_pNext;
9
10 if(pNext == NULL)
11 pReversedHead = pNode;
12
13 pNode->m_pNext = pPrev;
14
15 pPrev = pNode;
16 pNode = pNext;
17 }
18
19 return pReversedHead;
20 }

  当然,上面的源码中用到了四个指针,看完源码就会发现和上面分析的原理并没有相悖。或者下面这样也是可以的,两者的思路一致,没有差别。只不过下面的代码必须注意一点,跳出while循环的时候,最后一个结点的next域别忘记指向前一个结点,否则就会导致“断链”。

 1     ListNode* ReverseList(ListNode* pHead) {
2 ListNode *root=pHead;
3 ListNode *pre=NULL;
4 ListNode *next=NULL;
5 if(pHead==NULL) return NULL;
6 while(root->next){
7 next=root->next;
8 root->next=pre;
9 pre=root;
10 root=next;
11 }
12 root->next=pre;
13 return root;
14 }