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
- 开始时，first和last都指向head。
- 然后从 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;
}Related: rotterdam zoo animal list, strip light mounting brackets, la femme prom dresses near me, used ringmaster lathe for sale, apartments in alexandria, va under $1,300, le ciel de paris eiffel tower restaurant, earth rod installation cost, science diet large breed 6, mobile homes for sale in shelley, idaho, christina cosmetics official website, mens chelsea boots clearance sale, exotic fruit trees for sale near me, small aloe plant care, how to apply for housemaid visa in bahrain, radiology research opportunities for medical students,Related: dryer knob shaft broken, what does itira korgath metin mean, robert taylor obituary, estate agents jedburgh scottish borders, what values encourage misconduct, grainger county tomatoes shipped, buena vista correctional complex inmate mail, what is prestonplayz real phone number 2021, comcast cable box secret menu, hunt county property tax search, jani lane daughter died, douglas eugene franco cause of death, old testament disobedience and retribution examples, feels like i'm peeing my pants but i'm not, an ancient was spotted on the triple peninsula,Related: mebeverine and omeprazole together furosemide, beaver county accident yesterday, kathy keller obituary, pip enhanced mobility mental health 2021, signs a female doctor is attracted to you, discovery plus not working on sky q, how to stop my wandering eyes, will a 4x8 sheet of plywood fit in a tahoe, aldi pro heavy duty grout cleaner, accidentally sanded lead paint, robin trower wife, danielle bower abc, huski chocolate stockists uk, sa isang noontime show o pantanghalan variety show, tongue thrust exercises for adults,
作者：JarvisChu
原文链接：LeetCode-206-单链表逆序
版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0