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

(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,

版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0