【LeetCode】206.反转链表

题目

给你单链表的头节点 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;
    }
};

递归
比较难理解，这里给的是别人的题解

  /** * 以链表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;
    }