LeetCode206. Reverse Linked List（链表 / 模拟）

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日星期六