【LeetCode】206. Reverse linked list

题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表.

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转.你能否用两种方法解决这道题？

题解

使用迭代方法

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        ListNode* result = new ListNode(0);
        while(head)
        {
    
            ListNode* tmp = head;
            head = head->next;
            tmp->next = result->next;
            result->next = tmp;
        }
        return result->next;
    }
};

递归
比较难理解,Here is someone else's solution

  /** * 以链表1->2->3->4->5举例 */
    public ListNode* reverseList(ListNode* head) {
    
        if (head == null || head.next == null) {
    
            /* 直到当前节点的下一个节点为空时返回当前节点 由于5没有下一个节点了,所以此处返回节点5 */
            return head;
        }
        //递归传入下一个节点,目的是为了到达最后一个节点
        ListNode* newHead = reverseList(head.next);
                /* 第一轮出栈,head为5,head.next为空,返回5 第二轮出栈,head为4,head.next为5,执行head.next.next=head也就是5.next=4, 把当前节点的子节点的子节点指向当前节点 此时链表为1->2->3->4<->5,由于4与5互相指向,所以此处要断开4.next=null 此时链表为1->2->3->4<-5 返回节点5 第三轮出栈,head为3,head.next为4,执行head.next.next=head也就是4.next=3, 此时链表为1->2->3<->4<-5,由于3与4互相指向,所以此处要断开3.next=null 此时链表为1->2->3<-4<-5 返回节点5 第四轮出栈,head为2,head.next为3,执行head.next.next=head也就是3.next=2, 此时链表为1->2<->3<-4<-5,由于2与3互相指向,所以此处要断开2.next=null 此时链表为1->2<-3<-4<-5 返回节点5 第五轮出栈,head为1,head.next为2,执行head.next.next=head也就是2.next=1, 此时链表为1<->2<-3<-4<-5,由于1与2互相指向,所以此处要断开1.next=null 此时链表为1<-2<-3<-4<-5 返回节点5 出栈完成,最终头节点5->4->3->2->1 */
        head.next.next = head;
        head.next = null;
        return newHead;
    }