问题描述

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 插入法更精简写法

从所有递交结果中捞出的速度最快的算法

点击0位置的阴影块即可看到算法

思路和算法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