反转链表

要求

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

示例

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

输入:head = [1,2]
输出:[2,1]

输入:head = []
输出:[]

解答Ⅰ

使用迭代的方法,设置pre指针和cur指针,分别指向前一个和当前一个节点,想要让链表反转,只需将所有节点的next指针指向pre所指向的节点,但如果直接cur.next=pre,则会导致链表断开;所以需要事先使用一个临时变量next存储cur节点原先的下一个节点的值ListNode next = cur.next,再将当前节点的next指针指向pre所指的节点,接着右移pre指针指向cur所指的节点,再右移cur指针指向next;当cur指向了null,也就代表链表已经遍历完成,返回pre

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

3# 解答Ⅱ

使用递归的方法解决本题,本题反美诠释递归过程递和归的两个步骤,先递再归;递归终止的条件为head节点为空或者head节点的下一个节点为空,直接返回头节点;整体思路是通过函数嵌套找到最后一个节点,之后开始执行嵌套体内部的操作,将head节点下一个节点的next指针指向head本身--head.next.next = head,之后断裂原先head节点的next指针;向上递推,直到第一层函数判断head.next=null,返回head结束。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null; 
        return p;
    }
}

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

要求

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例

输入:head = [1,1,2]
输出:[1,2]
示例 2:

输入:head = [1,1,2,3,3]
输出:[1,2,3]

解答

得看清楚题目,不然会做复杂,存在一个按升序排列的链表;这就说明如果出现相同的元素,那么它们出现的位置一定是相邻的,依据这个条件,就可以判断cur.valcur.next.val是否相等了,如果相等就改变指针的指向(跳步),不等则直接连接即可;直到curnext指向null,返回head结束。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur!=null && cur.next!=null){
            if(cur.val==cur.next.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}

既然循环可以实现,那么递归一定也可以,只是感觉很繁琐

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next==null ){
            return head;
        }
        if(head.val==head.next.val){
            head.next = deleteDuplicates(head.next.next);
            return deleteDuplicates(head);
        }
        deleteDuplicates(head.next);
        return head;
    }
}