C++实现LeetCode(倒置链表)

[LeetCode] Reverse Linked List 倒置链表

Reverse a singly linked list.

Example:

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

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

 之前做到 Reverse Linked List II 的时候我还纳闷怎么只有二没有一呢，原来真是忘了啊，现在才加上，这道题跟之前那道比起来简单不少，题目为了增加些许难度，让我们分别用迭代和递归来实现，但难度还是不大。我们先来看迭代的解法，思路是在原链表之前建立一个空的newHead，因为首节点会变，然后从head开始，将之后的一个节点移到newHead之后，重复此操作直到head成为末节点为止，代码如下：

解法一：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newHead = NULL;
        while (head) {
            ListNode *t = head->next;
            head->next = newHead;
            newHead = head;
            head = t;
        }
        return newHead;
    }
};

下面我们来看递归解法，代码量更少，递归解法的思路是，不断的进入递归函数，直到head指向倒数第二个节点，因为head指向空或者是最后一个结点都直接返回了，newHead则指向对head的下一个结点调用递归函数返回的头结点，此时newHead指向最后一个结点，然后head的下一个结点的next指向head本身，这个相当于把head结点移动到末尾的操作，因为是回溯的操作，所以head的下一个结点总是在上一轮被移动到末尾了，但head之后的next还没有断开，所以可以顺势将head移动到末尾，再把next断开，最后返回newHead即可，代码如下：

解法二：

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

到此这篇关于C++实现LeetCode(倒置链表)的文章就介绍到这了,更多相关C++实现倒置链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(2.两个数字相加)

    [LeetCode] 2. Add Two Numbers 两个数字相加 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked

  • Java实现LeetCode（螺旋矩阵）

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • C++实现LeetCode(倒置链表之二)

    [LeetCode] 92. Reverse Linked List II 倒置链表之二 Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 很奇怪为何

  • C++实现leetcode(3.最长无重复字符的子串)

    [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", wit

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • C++实现LeetCode(倒置链表)

    [LeetCode] Reverse Linked List 倒置链表 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement

  • C++实现LeetCode(143.链表重排序)

    [LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 常见排序方法有

  • C++实现LeetCode(147.链表插入排序)

    C++实现LeetCode(147.链表插入排序)

    [LeetCode] 147. Insertion Sort List 链表插入排序 Sort a linked list using insertion sort. A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is

  • Leetcode常见链表问题及代码示例

    按规定区间反转链表 思路:可以考虑成一种把前后数字的结点断开重新组合的问题 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m,

  • C#数据结构之单链表(LinkList)实例详解

    C#数据结构之单链表(LinkList)实例详解

    本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data

  • Java双向链表倒置功能实现过程解析

    题目要求:Java实现一个双向链表的倒置功能(1->2->3 变成 3->2->1) 提交:代码.测试用例,希望可以写成一个Java小项目,可以看到单元测试部分 该题目的代码,已经放到了我的github上,地址为:https://github.com/jiashubing/alibaba-linkedlist-reversed.git 最关键的是自定义节点Node 和自定义双向链表MyLinkedList 两个类,倒置的方法放在自定义链表类里reversed() ,具体的说明都在代

  • C语言深入讲解链表的使用

    C语言深入讲解链表的使用

    目录 一.链表的概念 二.链表的分类 1. 单向或者双向链表 2. 带头或者不带头(是否有自带哨兵位头结点) 3. 循环或者非循环链表 4. 无头单向非循环链表和带头双向循环链表 3.链表的实现(代码和注释) 4.链表oj题(小试牛刀) 总结 现实生活中的火车就像一个完整的链表,现在我们来深入理解一下链表这个数据结构. 一.链表的概念 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 . 注: 1.从上图中可看出,链式结构在逻辑上是连续

  • C++实现算法两个数字相加详解

    Add Two Numbers 两个数字相加 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers

随机推荐