反转一个单链表.
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表. 你能否用两种方法解决这道题?
思路迭代 (麻烦版)
- struct ListNode* reverseList(struct ListNode* head) {
- struct ListNode* temp=head;
- struct ListNode* c=head;
- struct ListNode* reverse=head;
- if(head==NULL){
- return NULL;
- }
- int count=1;
- while(c->next!=NULL){
- count++;
- c=c->next;
- }
- int i=0;
- int a[count];
- while(temp!=NULL){
- a[i]=temp->val;
- i++;
- temp=temp->next;
- }
- for(int j=count-1;j>=0;--j){
- reverse->val=a[j];
- reverse=reverse->next;
- }
- return head;
- }
思路迭代 (简洁)
1->2 反转该链表, 1 的下一节点应指向 NULL, 事先需要用 temp 先保存 2, 这时新头节点 newHead 为 1, 下一循环, 然后针对节点 2 做同样操作, 2 的下一节点为 NULL, 接着设为节点 1
- struct ListNode* reverseList(struct ListNode* head) {
- struct ListNode* node=head;
- struct ListNode* newHead=NULL;
- struct ListNode* temp=NULL;
- while(node!=NULL){
- temp=node->next;
- node->next=newHead;
- newHead=node;
- node=temp;
- }
- return newHead;
- }
递归
先反转后面的链表, 从最后面的两个结点开始反转, 依次向前, 将后一个链表结点指向前一个结点, 注意每次反转后要将原链表中前一个结点的指针域置空
- struct ListNode* reverseList(struct ListNode* head) {
- // 如果链表为空或者链表中只有一个元素
- if(head==NULL||head->next==NULL){
- return head;
- }
- // 先反转后面的链表, 直到链表的末端结点
- struct ListNode* temp=reverseList(head->next);
- // 再将当前节点设置为后面节点的后续节点
- head->next->next=head;
- head->next=NULL;
- return temp;
- }
来源: http://www.jianshu.com/p/d3bac59e3e72