leetcode 206. Reverse Linked List (翻转一个链表)

题目要求 （高频题）

翻转一个链表，考虑使用迭代法和递归法。

输入示例

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

解题思路

本题和在数组中反转数字leetcode 7 Reverse Integer(翻转一个有符号的整数)的思路有些类似，但本质不同，由于存储地址不连续，使得我们不能直接利用位置（下标）信息实现操作。

在这里介绍一种翻转链表的常用方法:

1、三指针进行迭代，实现“头插法”。

最直接的想法就是，把一个链表的所有元素都倒过来，这里要借用一个空指针prv 指向空节点，第一步，我们希望节点1从单链表中剥离，于是让其指向 prv , 但我们不能因此而找不到链表索引，故需要一个额外的指针 nxt 指向节点1的后续节点，然后经过操作使得第一个节点指向prv，实现反向，接下来对剩余节点进行迭代操作即可。（看起来很像头插法构建链表）

迭代法 主要代码c++

/**
 * 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 * prv=NULL, *cur=head,*nxt; //当然你也可以直接用head而不是cur
        while(cur)
        {
            nxt = cur->next;
            cur->next = prv;
            prv = cur;
            cur = nxt;
        }       
        return prv; // 返回的是头指针指向的链表       
    }
};
           

2、递归法

思想是从后向前依次改变后继为前一个节点，所以不能从最后一个开始，一因为没办法记录最后一个节点的前驱，所以我们从倒数第二个节点开始，使得，最后一个节点的后继为倒数第二个（head->next->next = head; head->next=nullptr），然后再把倒数第二个节点的后继改为倒数第三个，依次递归的进行操作，即可。

过程示意图

递归法 主要代码c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {  
    	if(head==nullptr || head->next ==nullptr) return head;
    	ListNode *node = reverseList(head->next);
    	head->next->next = head; // 从倒数第二个元素开始递归的做倒序操作
    	head->next = nullptr;
    	return node;
     }
};
           

原题链接：https://leetcode.com/problems/reverse-linked-list/