字符串逆序
上次面试碰到一个单向链表逆序的题目,幸好对字符串逆序比较熟悉,类比做出来了。字符串逆序比较简单,直接上代码:
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;
}
|
至此结束了。