这篇文章给大家分享的是有关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”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!