Leetcode 206. Reverse Linked List

2019-11-10 18:32:06

字体：大中小

来源：转载

供稿：网友

Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

s思路： 1. 要求iterative和recursive. 2. 先来iterative。iterative写过几次了，简单的就是用dummy,然后PRe,pnow,pnext三个指针不停移动，交换！写完发现，dummy都省了，直接三个指针移位和交换就搞定了！ 3. 再来recursive: 这里写图片描述 x需要注意的是：代码写完后，检查在结尾的地方，也就是链表两头是否因为少了对指针清零等操作导致的cycle。如上图，就是1->2之间的指针没有清零，而2->1又建立起来，于是cycle!

//方法1：iterative.搞了半天，居然都不用加dummy。直接返回尾指针！class Solution {public: ListNode* reverseList(ListNode* head) { /*ListNode node(0); ListNode* dummy=&node; dummy->next=head;*/ ListNode* pre=NULL,*pnow=head,*pnext=NULL; while(pnow){ pnext=pnow->next; pnow->next=pre; if(!pnext) return pnow; pre=pnow; pnow=pnext; } return NULL; }};//方法2：recursive:class Solution {public: ListNode* reverseList(ListNode* head) { if(!head) return NULL; if(!head->next) return head; ListNode* tail=head->next; ListNode* newhead=reverseList(head->next); tail->next=head; head->next=NULL;//bug:没有这一句，就cycle.加上这一句，就cycle free return newhead; }};

上一篇：win10 uwp 如何拖动一个TextBlock的文字到另一个TextBlock

下一篇：5.1数组的定义&5.2数组的顺序表示和实现