206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解题思路：

头插法：

/* 执行用时 : 4 ms, 在Reverse Linked List的C提交中击败了99.40% 的用户 内存消耗 : 7.6 MB, 在Reverse Linked List的C提交中击败了17.55% 的用户 */ /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ //特殊情况进行判定 if(head == NULL || head->next == NULL)return head; //设置头节点，便于处理 struct ListNode* L; L = (struct ListNode*)malloc(sizeof(struct ListNode)); L->next = head; //头插法反转链表 struct ListNode* p=head->next,*q=NULL; head->next = NULL; while(p!=NULL){ q = p->next; p->next = L->next; L->next = p; p = q; } return L->next; }

直接反转： 

/* 执行时间:4ms */ /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ if(head == NULL){ return NULL; } struct ListNode* p = head;//工作指针，指向待反转结点 struct ListNode* pre = NULL;//记录已反转结点的首结点 struct ListNode* q = NULL;//保存待反转结点的下一个结点，防止丢失 //反转 while(p){ q = p->next; p->next = pre; pre = p; p = q; } return pPre; }

递归法：

/* 执行时间：12ms */ /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ //终止条件 if(head == NULL || head->next == NULL) return head; //递归 struct ListNode *p; p = reverseList(head->next); //反转 head->next->next = head; head->next = NULL; return p; }

后记：

掌握各种实现方法。