Chinaunix首页 | 论坛 | 博客

分类: C/C++

2018-07-08 17:11:32

今天介绍两道面试时经常被问到的链表问题:
1. 翻转链表
2. 两两交换链表元素(假定有偶数个元素),只能操作指针
注:每个节点的结构如下所示:

点击(此处)折叠或打开

  1. struct Node{
  2.     int val;
  3.     struct Node *pNext;
  4.     Node(int x):val(x), pNext(NULL){}
  5. };


解:1 倒查法:
代码如下,其中为了记录下一个要被插入的元素,需要使用指针next记录之:

点击(此处)折叠或打开

  1. void ReverseList(struct Node *&head){
  2.     if(head== NULL) return;
  3.     struct Node *trav = head->pNext, *next;
  4.     head->pNext = NULL;
  5.     while(trav){
  6.         next = trav->pNext;
  7.         trav->pNext = head;
  8.         head = trav;
  9.         trav=next;
  10.     }
  11. }
插入前后对照图如下:


2. 代码如下,这次需要记录当前交换的两个元素的前一个元素,这里使用指针pre来实现:

点击(此处)折叠或打开

  1. void ReverseAdjTwo(struct Node *&head){
  2.     if(head == NULL) return;
  3.     struct Node *first = head;
  4.     struct Node *second = first->pNext;
  5.     // first two element
  6.     first->pNext = second->pNext;
  7.     second->pNext = first;
  8.     head = second;
  9.     struct Node *pre = first;
  10.     first = first->pNext;
  11.     while(first){
  12.         second = first->pNext;
  13.         pre->pNext = second;
  14.         first->pNext = second->pNext;
  15.         second->pNext = first;
  16.         pre = first;
  17.         first = first->pNext;
  18.     }
  19. }
每一轮处理前后对比如下图:

这里,由于头结点两个没有pre,需要特殊处理一下~~~
阅读(13) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册