206. 反转链表

1.题目

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

2.示例

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

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

3.答案

①递归

停止条件:链表为空或者只有一个元素
递归内容： 翻转链头之后元素，将当前链头设置为链尾
返回值：反转链表的新链头节点

 ListNode* reverseList(ListNode* head) {
        //递归
        if(!head||!head->next) return head;
        ListNode *tmp=reverseList(head->next);
        // 这里 head->next之后结点的指针都进行了翻转，但是 head->next还没有进行改变
        head->next->next=head;
        //作为尾结点
        head->next=nullptr;
        return tmp;  //返回新的头结点
    }
1
2
3
4
5
6
7
8
9
10

②迭代

一个指针一个的翻转

 ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode *pre=nullptr,* cur=head;
        while(cur){
        //记录下一个指针
            ListNode * tmp=cur->next;
            //向前指
            cur->next=pre;
			//向后前进
            pre=cur;
            cur=tmp;
        }
        return pre;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15