leetcode 206. Reverse Linked List

LeetCode


  1. Reverse Linked List:题目链接

方法1：反转指针 (推荐)

基本思想： 从开始节点开始将其指针域指向其前驱，这时为了防止断链需要一个指针nextNode记住当前节点的后继节点

  1. 第一个节点的指针域应置为NULL，作为反转链表后的表尾
  2. 处理完最后一个节点时，要将头结点指向它
  • cur:指向当前所在节点 初始化：head
  • pre:cur的前驱节点 初始化：NULL
  • nextNode: cur的后继节点 简称q
原理

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 时间复杂度O(N)  空间复杂度O(1)
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode*curNode = dummyHead->next, *pre = NULL, *nextNode = NULL;   // 注意*pre = NULL 方便将第一个有效节点的指针域置为NULL(新的表尾)
    while (curNode != NULL) {
        nextNode = curNode->next;
        curNode->next = pre;            // 反转指针
        pre = curNode;                  // 更新pre
        curNode = nextNode;             // 更新curNode
    }
    dummyHead->next = pre;              // 此时pre指向链表最后一个元素 将反转后的链表挂到头结点后面
    return dummyHead->next;
}

方法2：头插法

基本思想：将头节点摘下，然后从开始节点开始，依次前插到头结点后面(头插法建立链表,栈)，直到最后一个节点为止，注意这里将节点插入到头结点后，开始节点前

1
2
3
4
5
6
7
初始时：dummy -> 1 -> 2 -> 3 -> 4 -> 5
dummy -> NULL  先将头指针的指针域置为NULL   剩下的链表为： 1 -> 2 -> 3 -> 4 -> 5
dummy -> 1                          依次前插到头结点后面
dummy -> 2 -> 1
dummy -> 3 -> 2 -> 1
dummy -> 4 -> 3 -> 2 -> 1
dummy -> 5 -> 4 -> 3 -> 2 -> 1

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 时间复杂度O(N)  空间复杂度O(1)  头插法(栈)
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* dummy = (struct ListNode*) malloc (sizeof(struct ListNode));
    dummy->next = head;
    
    struct ListNode* curNode = dummy->next , *nextNode = NULL;
    dummy->next = NULL;
    while (curNode != NULL) {
        nextNode = curNode->next;
        curNode->next = dummy->next;
        dummy->next = curNode;
        curNode = nextNode;
    }
    return dummy->next;
}

方法3：递归

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
// 时间复杂度O(N)  空间复杂度O(N)
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next==NULL) {
        return head;
    }
    struct ListNode * newHead = reverseList(head->next);
    // head->next此刻指向head后面的链表的尾节点
    // head->next->next = head把head节点放在了尾部
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

pS: 源代码链接

本文标题:leetcode 206. Reverse Linked List

文章作者:XerDemo

发布时间:2018-09-16, 17:44:53

最后更新:2019-07-22, 19:12:29

原始链接:https://xerdemo.github.io/2018/09/16/leetcode-206-Reverse-Linked-List/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 方法1：反转指针 (推荐)
  2. 2. 方法2：头插法
  3. 3. 方法3：递归
|