Linked List - Reverse Linked List

by LauCyun Sep 20,2014 18:04:26 4,195 views

Question

Problem Statement

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

题解1 - 非递归

分析由1->2->3变为3->2->1的过程,由于是单向链表,故只能由1开始遍历,1和2最开始的位置是1->2,最后变为2->1,故从这里开始寻找突破口,探讨如何交换1和2的节点:

temp = head->next;
head->next = prev;
prev = head;
head = temp;

要点在于维护两个指针变量prevhead, 翻转相邻两个节点之前保存下一节点的值,分析如下图所示:

可归纳为:

  • 保存head下一节点
  • 将head所指向的下一节点改为prev
  • 将prev替换为head,波浪式前进
  • 将第一步保存的下一节点替换为head,用于下一次循环

C

/**
 * 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 *prev = NULL, *temp = NULL;
    while (head != NULL) {
        temp = head->next;
        head->next = prev;
        prev = head;
        head = temp;
    }
    // fix head, because head is NULL at this time
    head = prev;
    return head;
}

源码分析

题解中基本分析完毕,代码中的prev赋值比较精炼,值得借鉴。

复杂度分析

遍历一次链表,时间复杂度为\(O(n)\),使用了辅助变量,空间复杂度\(O(1)\)

题解2 - 递归

递归的终止步分三种情况讨论:

  1. 原链表为空,直接返回空链表即可。
  2. 原链表仅有一个元素,返回该元素。
  3. 原链表有两个以上元素,由于是单链表,故翻转需要自尾部向首部逆推。

由尾部向首部逆推时大致步骤为先翻转当前节点和下一节点,然后将当前节点指向的下一节点置空(否则会出现死循环和新生成的链表尾节点不指向空),如此递归到头节点为止。新链表的头节点在整个递归过程中一直没有变化,逐层向上返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *reverseList(struct ListNode *head) {
    // case1: empty list
    if (head == NULL) {
        return NULL;
    }
    // case2: only one element list
    else if (head->next == NULL) {
        return head;
    }
    // case3: reverse from the rest after head
    struct ListNode *newHead = reverseList(head->next);
    // reverse between head and head->next
    head->next->next = head;
    // unlink list from the rest
    head->next = NULL;
    return newHead;
}

源码分析

case1 和 case2 可以合在一起考虑,case3 返回的为新链表的头节点,整个递归过程中保持不变。

复杂度分析

递归嵌套层数为\(O(n)\),时间复杂度为\(O(n)\),空间(不含栈空间)复杂度为\(O(1)\)

Reference

Tags