LeetCode-206-单链表逆序
问题描述
LeetCode – Reverse Linked List
将单链表逆序
算法1 – 插入法
性能:Runtime: 4 ms, faster than 89.98% of C online submissions for Reverse Linked List.
算法思路:类比于插入排序,两个指针 first 和 last 分别指向已经逆序好的开头和结尾,即 first->x->x->last->NULL
1. 开始时,first和last都指向head。
2. 然后从 head->next 开始,遍历链表,将每个节点 p 插入到(first,last)的开头,即p->fist->x->x->NULL
代码如下
struct ListNode* reverseList(struct ListNode* head){ if (head->next == NULL) return head; struct ListNode* first = head; // (first, last) 是已经逆序的部分,first->xx->last struct ListNode* last = head; // 遍历链表,往前插入 struct ListNode* p = head->next; last->next = NULL; while(p != NULL) { // first->xxx->head, 插入p,变为 p->first->xx->head struct ListNode* pNext = p->next; // 先记录p->next p->next = first; first = p; p = pNext; } return first; }
C solution fast than 89.98%, Similar to Insert Sort algorithm
算法2 新增一个头节点pre,不断将数据插入pre后面
C++ Iterative and Recursive
这是discuss区一个vote较高的答案,思路和我的算法很像,都是插入。
不过,它是新增了一个头结点pre,然后遍历链表,不断的把节点,插入到pre后面
(1) 新增节点pre, pre->next 指向 head, 即 (pre->head)
(2) cur 指向 head,不断的把 cur->next 插入到 pre 和 head 之间. ( cur 位置不变,始终是指向head的。但是随着插入的进行,cur->next 不断往后了)
比如原List是 1->2->3->4->NULL,那么新增一个pre,变成pre->1->2->3->4->NULL,cur始终指向head,即 1,但是随着插入的进行,cur->next 依次变成了2,3,4
代码
struct ListNode* reverseList(struct ListNode* head) { struct ListNode *pre = malloc(sizeof(struct ListNode)); struct ListNode *cur = head; pre -> next = head; while (cur && cur -> next) { struct ListNode* temp = pre -> next; pre -> next = cur -> next; cur -> next = cur -> next -> next; pre -> next -> next = temp; } return pre -> next; }
算法4 插入法更精简写法
从所有递交结果中捞出的速度最快的算法
思路和算法1一样,相当于 prev 就是first,head就是last。只是更精简而已。
(prev, head) 是已经逆序的,然后不断head往后走,然后把head->next插入到开头。
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL || head->next == NULL) return head; struct ListNode* prev = NULL; while (head != NULL) { struct ListNode* temp = head; head = head->next; temp->next = prev; prev = temp; } return prev; }
算法5 递归
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL || head->next == NULL) return head; struct ListNode* node = reverseList(head->next); if (head->next->next == NULL) printf("NULL\n"); head->next->next = head; // head->next 就是 node所逆序链表的最后一个元素 head->next = NULL; return node; }
作者:JarvisChu
原文链接:LeetCode-206-单链表逆序
版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0