反转链表（图文讲解）

---

---

一、反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
反转链表主要有三种方法：头插、迭代和递归。
这里我主要介绍头插和迭代。

---

1.头插

思路：将原链表的节点逐个放下来，头插入newhead链表。另外，因为改变了节点的next的指向，还得定义一个next来保存下个地址。
将newhead定义为NULL，为新的头节点。

将cur->next指向newhead,然后将newhead移到cur的位置，再改cur为next,往下走。当cur走到NULL，就结束了。

代码如下：

struct ListNode* reverseList(struct ListNode* head){
//头插
struct ListNode*cur,*newhead,*next;
if(head==NULL)//注意空链表
{
    return head;
}
cur=head;
newhead=NULL;
next=cur->next;
while(cur)
{
    cur->next=newhead;
    newhead=cur;
    cur=next;
    if(cur!=NULL)//注意，防止next越界访问
    next=cur->next;
}
return newhead;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.迭代

思路：单链表的方向都是沿着同一方向的，那我们就直接改变它的方向

将cur->next指向prev,然后prev,cur,next依次往后迭代走。当cur为空指针时，迭代结束，此时prev为新链表的头节点

完整流程：

代码如下：

struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)//空链表
return head;
struct ListNode*prev,*cur,*next;
prev=NULL;
cur=head;
 next=head->next;
while(cur)
{
    cur->next=prev;//反转
    prev=cur;//迭代
    cur=next;
    if(next!=NULL)//结束时n2为NULL，不能再->
    next=cur->next;

}
return prev;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

二、注意事项

关于链表的题目大多需要思考传入的链表为不为空，使用多指针时，注意是否存在指针越界访问的问题。好了，这次就到这里了，有什么不对的还请多多指教。