1. 题目描述
2. 思路分析
方法一:三指针翻转法
使用三个结构体指针n1,n2,n3,原地修改结点指向。
就是让n1先指向空指针NULL,n2指向头结点,n3指向头结点下一个结点。
用n2进行遍历。然后让n1指向n2,n2指向n3,n3指向n3的下一个结点。如此循环遍历,直到n2指向空指针NULL时停止。
最后返回n1即可。
这里为什么要用三个指针呢?
因为如果只用两个指针,那么我们让n1指向n2后,链表的连接就断了,找不到原链表n2的下一个结点了。
同时,我们需要注意一些临界条件和特殊情况。
比如链表是空的,我们就让最后返回空即可。
一般情况至少有一个结点存在,所以我们得在n2不为空的情况下(即if(n2)),让n3指向n2的下一个结点。(n3=n2->next)
遍历过程中,n3要指向下一个结点,那么n3就不能是空指针(即if(n3) n3=n3->next)
方法二:头插法
对每一个结点都进行头插
3. 代码实现
方法一:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *n1,*n2,*n3;
n1=NULL;
n2=head;
if(n2)
n3=n2->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
方法二:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *cur=head;
struct ListNode *newhead=NULL;
while(cur)
{
struct ListNode *next=cur->next;
//头插
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}