day03

leetcode203. 移除链表元素

删除链表中的一个节点分为两种情况 ，节点是头结点和不是头结点

两种方法

方法1：头结点和其他节点分开处理

class Solution {    //不使用虚拟头结点方法
    public ListNode removeElements(ListNode head, int val) {
        while(head!=null&&head.val==val){      //头部元素提前处理，处理完后  head不存在等于val情况
            head=head.next;
        }
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){       //cur指向头部开始  cur  不能等于null且cur.next不能等于null              cur充当  要删除节点的 前节点
            if(cur.next.val==val){
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
        return head;
    }
}

方法2：设置虚拟头结点

//设置虚拟头结点的作用是使头节点和其他节点的处理方式一样
class Solution {    //不使用虚拟头结点方法
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyhead=new ListNode(-1,head);
        ListNode cur=dummyhead;      //设置头结点    
        while(cur.next!=null){
            if(cur.next.val==val){
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
        return dummyhead.next;
    }
}

LeetCode：206.反转链表

//双指针法
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode pred=null;


        while(cur!=null){
            ListNode temp=cur.next;      //temp保存  cur之后的指向 防止断连
            cur.next=pred;              //反转cur 的指向 反转链表
            pred=cur;                   //pred  到下一个位置 也就是 cur
            cur=temp;           //cur 到下一个位置    也就是 一开始 temp的位置
        }
        return  cur;    //经过遍历之后 cur 指向了null 最后终止循环， 所以  头节点应该是pred

//反转一个节点的顺序 ：
//  1：先把该节点的下一个节点保存
//  2：反转该节点的方向
//  3： 该节点的前一个指针（先移动pred 再移动cur） 和当前指针向后移动一位  遍历到下一个节点
    }
}

//递归写法
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    private ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null){
            return pre;
        }
        ListNode temp=cur.next;
        cur.next=pre;
        return reverse(cur,temp);
    }
}