链表必刷题第一部分

206.反转链表

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

解题思路一：迭代法

迭代方法的关键在于使用三个指针（prev, curr, next）来遍历链表，依次修改指针的指向。详细步骤如下：

1. 初始化三个指针：prev 指向空（null），curr 指向链表头部，next 指向空（null）。
2. 遍历链表：
   • 在每一次迭代中，首先将 curr 的下一个节点保存到 next。
   • 然后修改 curr 的下一个节点指向 prev，实现反转。
   • 更新 prev 和 curr 指针，将它们向前移动一个节点。
   • 重复这个过程直到 curr 为空。
3. 当迭代结束时，prev 指向反转后的链表头部。

解题思路二：递归法

递归方法的关键在于从最后一个节点开始反转，并且在递归过程中修改指针的指向。详细步骤如下：

1. 如果当前节点（head）为空或者其下一个节点为空，直接返回当前节点（递归的基本情况）。
2. 反转从当前节点的下一个节点开始的子链表，并将返回的新头部赋值给 new_head。
3. 修改当前节点的下一个节点的指向为当前节点，即 head.next.next = head。
4. 将当前节点的下一个节点设为空，即 head.next = null。
5. 返回新的头部节点 new_head。

// 迭代法
ListNode* reverseList(ListNode* head) {
    ListNode *cur = head, *pre = nullptr, *next = nullptr;
    while(cur != nullptr) {
        next = cur-> next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

// 递归法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* new_head = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return new_head;
    }
};

// 迭代法
class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;

        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
}

// 递归法
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode new_head = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return new_head;
    }
}

// 迭代法
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    var next *ListNode

    for curr != nil {
        next = curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

// 递归法
func reverseList(head *ListNode) *ListNode {
    if head==nil||head.Next==nil{
        return head
    }
    last := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}

---

83.删除排序链表中的重复元素

给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

解题思路一：迭代法

删除排序链表中的重复元素的思路是遍历链表，并比较相邻的节点，如果两个相邻节点的值相同，则删除其中一个。详细步骤如下：

1. 初始化一个指针 curr 指向链表头部。
2. 遍历链表：
   • 比较 curr 节点和 curr 的下一个节点的值：
     • 如果值相同，则将 curr 的下一个节点指向下一个的下一个节点（即删除 curr 的下一个节点）。
     • 如果值不同，则将 curr 指针向前移动一个节点。
   • 重复这个过程直到 curr 或者 curr 的下一个节点为空。
3. 返回链表头部节点。

解题思路二：递归法

递归删除排序链表中的重复元素的思路是将问题分解为两部分：首先处理头节点及其重复元素，然后递归处理剩余链表。这种方法的关键在于利用递归处理子链表，并将结果链接到当前节点。详细步骤如下：

1. 递归的基本情况：如果链表为空（head 为 None）或者链表只有一个节点（head.next 为 None），直接返回 head。
2. 递归调用：将 head.next 传递给递归函数，将返回的结果赋值给 head.next。
3. 比较当前节点（head）和其下一个节点（head.next）的值：
   • 如果值相同，说明存在重复元素，此时将当前节点的下一个节点指向下一个的下一个节点（即删除 head 的下一个节点），并保持当前节点不变。
   • 如果值不同，说明不存在重复元素，直接返回当前节点。
4. 返回链表头部节点。

//迭代法
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* curr = head;

        while (curr != nullptr && curr->next != nullptr) {
            if (curr->val == curr->next->val) {
                curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }

        return head;
    }
};

// 递归法
class Solution {
public: