关于链表的一些技巧

链表的结构比较简单,基本特性以及相关操作这里就不作介绍。如果有同学不自信的话,这有个pdf文档可以参考复习下。http://cslibrary.stanford.edu/103/如果有同学网络问题不给力的话,可以给我发邮件。下面来看几道常见的面试题。

1.链表倒置(两种方法)

这个应该也算比较简单的,直接上代码了。(两种:迭代、递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void reverse_iterate(struct node** head)
{

  struct node* result = NULL;
  struct node* current = *head;
  struct node* next;

  while(current != NULL)
  {
  next = current->next;

  current->next = result;
  result = current;
  current = next;
  }
  *head = result;
}

void reverse_recursive(struct node** head)
{

  struct node* first;
  struct node* rest;

  if(*head == NULL)
  return;

  first = head;
  rest = first->next;

  if(rest == NULL)
  return;

  reverse_recursive(& rest);

  first->next->next = first;
  first->next = NULL;

  *head = rest;
}

2.把一个链表拆为两半,要求只遍历一次

比如链表{1,2,3,4,5},前半部分为{1,2,3}, 后半部分为{4,5}。如果要求只遍历一次的话,我们只需找到中间点就可以。那么我们不妨使用两个指针(point fast/low),遍历的步长一个为另一个的2倍。代码简单实现如下(已经考虑了链表长度为奇数的情况)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void front_back_split(struct node* head, struct node** frontRef, struct node** backRef)
{

  struct node* fast;
  struct node* low;

  if(head==NULL || head->next==NULL)
  {
  *frontRef = head;
  *backRef = NULL;
  }
  else
  {
  fast = head;
  slow = head;
  while(fast != NULL)
  {
  fast = fast->next;
  if(fast != NULL)
  {
  fast = fast->next;
  slow = slow->next;
  }
  }
  }

  frontRef = head;
  backRef = slow->next;
}

3.判断一个单链表是否有环

通过第二题,同学们可能有些思路。方法是类似的。检测环的这种方法称为Floyd’s cycle finding algorithm,链接为en.wiki。方法简述一下,代码就不写了,wiki中比较详细些。设置两个指针fast,low指向表头,low每次移动一步,fast每次移动两步。如果链表不存在环,fast最终为null。如果存在环,最终两指针将在环中循环,总会相交。也就是,若两指针相交,那么单链表中存在环。

问题还没有结束,针对问题3,如何找到环的入口呢?其实这个通过数学简单思考一个就可以了。链表的长度为环的长度加上表头到入口的长度。我们可以轻松求得环的长度:fast,low指针相交后继续移动,下次相交的时候fast比low多走了一圈,又fast的速度为low的2倍。也就是说low指针移动的步数就是圈的长度(怎么有点像小学生数学应用题,小学数学V5..),记为x。将fast,low指针重置到表头,这次还是fast先移动,但是fast移动x步之后,low才开始移动,且fast和low的速度都为1,则fast和low指针再次相遇的时候就是环的入口处,想一想,是不是?