[数据结构与算法]leetcode刷题 (5.9)链表

1. 反转链表

206

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

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

思路：改变链表指针的指向，不用重新创建一个链表，浪费内存。
双指针法，递归法（与双指针一样，除了不用更新两个指针向前走）

笔记：
C++:
从后往前迭代有点想不通，抓住：
迭代函数return的是新链表的head，迭代函数调用时按从前往后的顺序不断给他喂。

C++：

// 双指针法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p = head;
        ListNode* pre = nullptr;
        ListNode* tmp;
        while(p){
            // 保存p的下一结点，因为p改指向后会找不到
            tmp = p->next;
            p->next = pre;
            //两个指针往前走
            pre = p;
            p = tmp;   
        } 
        return pre;   //返回头结点
    }
};

// 从前往后递归法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }

    ListNode* reverse(ListNode* pre, ListNode* p){
        if(p == nullptr)  return pre;
        ListNode* tmp = p->next;
        p->next = pre;
        return reverse(p, tmp);  //相当于更新向前走
    }
};

// 从后往前递归反转
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 空链表
        if(head == NULL)    return NULL;
        // 递归到head为最后一个结点时，将他设为头结点
        if(head->next == NULL)  return head;

        // 递归顺序为(从最里层到外): head=5,4,3,2,1
        ListNode* last = reverseList(head->next);
        // 反转：将head->next指向head
        head->next->next = head;
        // head指向空
        head->next = NULL;
        // 返回的last是新链表的头结点(5,5,5,5,5)
        return last;
    }
};

Python：

# 双指针法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        p = head
        pre = None
        while(p!=None):
            tmp = p.next
            p.next = pre
            pre = p
            p = tmp
        return pre

# 从前往后迭代
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:

        def reverse(pre, p):
            if not p:
                return pre
            tmp = p.next
            p.next = pre

            return reverse(p, tmp)
        
        return reverse(None, head)

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖