字符串逆序
上次面试碰到一个单向链表逆序的题目，幸好对字符串逆序比较熟悉，类比做出来了。字符串逆序比较简单，直接上代码：
|
1
2
3
4
5
6
7
8
9
10
|
void stringReverse(char* p1,char* p2) { if(p1==p2)return; //swap the value of p1 ,p2 *p1=(*p1)+(*p2); *p2=(*p1)-(*p2); *p1=(*p1)-(*p2); if(p1==p2-1)return; else stringReverse(++p1,--p2); } |
调用示例：
|
1
|
stringReverse(str,str+strlen(str)-1); |
单向链表逆序
先上三幅图：原始状态是图一，全部逆序之后是图三的样子，图二是逆序一步之后的样子。按照图二的步骤依次往后，每次移动一步，把p1->next 反向，直到全部逆序。详细原理请看代码。
图一：
图二：
图三：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
typedef struct Node Node; struct Node{ int data; Node* next; }; Node* reverseLinkList(Node* head){ if (head==NULL||head->next==NULL) { return head; } Node* p1 = head; Node* p2 = p1->next; Node* p3 = p2->next; p1->next = NULL;//p1要变成尾指针，所以指向NULL while (p3!=NULL) { p2->next = p1;//p2->next 反向 p1=p2;//p1指针向后移动一步 p2=p3;//p2指针向后移动一步 p3=p3->next;//p3指针向后移动一步 } p2->next=p1;//p3指向了NULL，p2反向 head=p2;//头指针指向之前的尾指针 return head; } |
至此结束了。
