[C/C++]数据结构 链表OJ题: 反转链表

描述:

        给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

示例:

 

方法一:    让链表指向反向

如图所示:

代码思路:

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* n1=NULL;struct ListNode* n2=head;struct ListNode* n3=head->next;while(n2){//n2指向n1n2->next=n1;//三个指针向后移动n1=n2;n2=n3;n3=n3->next;}return n1;
}

这里要注意,上述代码是我们通过画图写出来的大概思路,这里还有特殊情况需要处理一下,

比如:

•  struct ListNode* n3=head->next;
•  n3=n3->next;

开始并没有判断head和n3指针是否为空,直接引用next可能会导致错误

正确代码:

struct ListNode* reverseList(struct ListNode* head) {//空链表反转后还是空链表if(head==NULL){return NULL;}struct ListNode* n1=NULL;struct ListNode* n2=head;struct ListNode* n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;//如果n3指向空的话就说明走到链表末尾了,没必要在往后走了if(n3)n3=n3->next;}return n1;
}

方法二:  头插法

从开始依次取出结点,按头插法插入,就可以实现链表反转

代码:

struct ListNode* reverseList(struct ListNode* head) {if(head==NULL){return NULL;}struct ListNode* cur=head;struct ListNode* newNode=NULL;while(cur){struct ListNode*ret=cur->next;cur->next=newNode;newNode=cur;cur=ret;}return newNode;}