反转链表

题目链接

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

20220109101423-2022-01-09-10-14-24

示例:

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

思路

解法一：

递归解法

解题的重点在于如何反转

假设总的链表为 p1 -> p2 -> p3 ->p4 -> p5 -> ∅

p3-p5 已反转,如下所示： p1 -> p2 -> p3 <-p4 <- p5

p3 的下一节点指向 p2,即 p2->next->next = p3

同时head的next指向∅

整个递归过程如下：

reverseList: head=p1
    reverseList: head=p2
	    reverseList: head=p3
		    reverseList:head=p4
			    reverseList:head=p5 
					终止返回
				cur = p5
				p4.next.next->p4，即 p5->p4
			cur=p5
			p3.next.next->p3，即 p4->p3
		cur = p5
		p2.next.next->p2，即 p3->p2
	cur = p5
	p1.next.next->p1，即 p2->p1

解法二：

迭代解法

整个链表的反转可分解成两个 Node 节点的反转，所以需要三个指针元素来完成。分别定义为三个相邻指针 pre, cur, next, 其中， pre 定义为空指针，cur 指向 head 节点，next 为 cur 的下一个节点，依次进行反转，反转后移动指针，直至 cur 指针为空，返回 pre 指针。

其中，需要注意指针的顺序。

cur->next = pre; 
pre = cur;
cur = next;

题解

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head -> next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};