【LeetCode】 链表

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

题目描述

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

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

方法一 迭代

思路

遍历结点，如果当前结点值和下一个结点值相等，则删除下一个结点；否则继续遍历下一个结点

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *p = head;
        while(p!=NULL and p->next!=NULL){
            if(p->next->val==p->val){
                p->next = p->next->next;
  
            }
            else{
                p = p->next;
            }
        }
        
        return head;
        
    }
};

方法二 递归

思路

递归我们不用纠结每一级调用和返回的细节，做递归我们只需要关注以下三点：

• 整个递归的终止条件：递归应该在什么时候结束
• 本级递归需要做什么：在这一级递归中应该完成什么任务
• 找返回值：应该给上一级返回什么信息

比如这道题我们的终止条件就是head指向链表只剩下一个元素的时候，这个时候只有一个结点则不存在重复了；第二步，我们在本级递归需判断当前的值和下一个结点的值是否重复；第三步：返回的是当前的head

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        
        //第一步：找终止条件，head指向链表只剩下一个元素的时候
        if(head==NULL or head->next==NULL){
            return head;
        }
        //第二步: 本级递归需要做什么
        head->next = deleteDuplicates(head->next);
        if(head->val==head->next->val){
            head = head->next;
        }
        //第三步：返回值是什么
        return head;
    }
};

24. 两两交换链表中的节点

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

方法一：递归

思路

递归的套路：

• 整个递归的终止条件：只剩下一个结点或者没结点了就没得交换了 ，返回已经处理好的链表
• 当前递归要做什么：对我们来说本级递归只有head、head->next和已经处理完的链表部分，我们要做的就是把这三个节点中的前两个结点交换
  
• 返回给上一级的应该是已经交换好的链表

代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        //整个递归的终止条件：只剩下一个结点或者没结点了就没得交换了 ，返回已经处理好的链表
        if(head==NULL or head->next==NULL){
            return head;
        }
        
        //由于递归只考虑本级递归，所以对我们来说本级递归只有head、head->next和已经处理完的链表部分
        //我们要做的就是把这三个节点中的前两个结点交换
        
        ListNode *next = head->next;
        head->next = swapPairs(head->next->next);
        next->next = head;
        
        //返回给上一级的应该是已经交换好的链表
        return next;
        
    }
};