MENU

LeetCode206. Reverse Linked List(链表 / 模拟)

2019 年 01 月 26 日 • 阅读: 1212 • LeetCode阅读设置

LeetCode206. Reverse Linked List(模拟)

  • Easy
  • Accepted:489,742
  • Submissions:944,280

Description

Reverse a singly linked list.

Example

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

链接

https://leetcode.com/problems/reverse-linked-list/

题意

翻转链表。

题解

熟悉链表的话还是很好写的,直接模拟就好了,但是不熟悉的话就得花些时间理解一下,最好自己画图过一遍。我的做法是:用headNew表示新链表表头,tmp保存head指向的结点,然后在对链表进行遍历时,先让head指向headNew,然后headNew保存head内容,这样操作就实现了倒序保存,再让head指向下一个结点,循环操作直至链表结点为空。

  • 初始链表

  • 初始指针

  • 变化过程

代码

  • Runtime: 4 ms, faster than 100.00% of C++ online submissions for Reverse Linked List.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* headNew = NULL; // 新链表表头
        ListNode* tmp = NULL; // 临时指针
        while (head)
        {
            tmp = head->next; // 保存head指向的结点
            head->next = headNew;
            headNew = head; 
            head = tmp; // 即指向head的下一个结点
        }
        return headNew;
    }
};

// 规范化写法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head; // 当前节点
        ListNode* headNew = NULL; // 新链表表头
        while (cur != NULL)
        {
            ListNode* next = cur->next; // 后移
            cur->next = headNew; // 倒转
            headNew = cur;
            cur = next;
        }
        return headNew;
    }
};

理解之后还是很好写的,还有一种递归写法,晚点再补上。

补上递归版,跟着模拟一下就能理解了,具体可以参考Grandyang的博客

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next)
            return head;
        ListNode* headNew = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return headNew;
    }
};

测试

#include <bits/stdc++.h>
using namespace std;

// 链表节点
struct ListNode
{
    int val;
    ListNode * next;
    ListNode(int x): val(x), next(NULL) {}
};

// 创建链表
ListNode* createLinkedList(int arr[], int n)
{
    if (n == 0)
        return NULL;
    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for (int i = 1; i < n; ++i)
    {
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }
    return head;
}

//打印链表
void printLinkedList(ListNode* head)
{
    ListNode* curNode = head;
    while (curNode != NULL)
    {
        cout << curNode->val << " -> ";
        curNode = curNode->next;
    }
    cout << "NULL" << endl;
}

// 翻转链表
ListNode *reverseList(ListNode *head)
{
    ListNode *cur = head; // 当前节点
    ListNode *headNew = NULL; // 新链表表头
    while (cur != NULL)
    {
        ListNode *next = cur->next; // 后移
        cur->next = headNew; // 倒转
        headNew = cur;
        cur = next;
    }
    return headNew;
}

// 删除链表
void deleteLinkedList(ListNode* head)
{
    ListNode* curNode = head;
    while (curNode != NULL)
    {
        ListNode* delNode = curNode;
        curNode = curNode->next;
        delete  delNode;
    }
}

int main()
{
    int n = 6;
    int arr[10];
    for (int i = 0; i < n; ++i)
        arr[i] = rand() % 20 ;
    ListNode* head = createLinkedList(arr, n);
    printLinkedList(head);
    ListNode* reverseHead = reverseList(head);
    printLinkedList(reverseHead);
    deleteLinkedList(reverseHead);
    return 0;
}

The end.

2019年1月26日 星期六

最后编辑于: 2020 年 04 月 24 日