Day3| 203.移除链表元素 & 707.设计链表 & 206.反转链表

前两天发烧了,这几天没更的后续会补齐

链表结构如下

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

203.移除链表元素

题目:给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

思路:分为几个步骤来考虑.

步骤1 : 头结点等于val,那么就将头结点后移,直到头结点等于null跳出循环

步骤2 : 这时候拿到的头结点是值不为val的头结点,考虑后面的元素里面有没有值为val的节点即可

步骤3 : 如果这个时候拿到的头结点的值不为val但是为null,那么说明链表已经遍历完毕,并且删除了全部的相同元素或者传入的参数head即为null,那么这时候return null即可

步骤4 :如果不满足步骤3,那么则进入步骤4,这时候考虑到要使用一个移动的指针来取出链表中的每个数据进行比较,因此就只能声明一个新的ListNode类型的变量tmp来储存我想用的指针,我让这个指针在最开始指向head这个节点.

步骤5 : 接着我就要考虑如何利用tmp这个指针边遍历边比较了.我是这么考虑的,tmp指针最开始指向了head节点,由于步骤2已经为我排除了头结点等于val的可能性,因此我现在直接判断tmp.next.val是否等于val,如果等于将tmp.next指向tmp.next.next,即跳过需要删除的节点即可,此时指针还在原来的位置,因为已经删除完毕,tmp现在位置的下一个节点已经更新,这时候下个循环需要比较的还是tmp.next,因此tmp的位置不应该有任何变化.这部分应该放进循环

步骤6 : 刚才的情况是tmp.next.val=val的情况,现在要考虑tmp.next.val不等于val的情况,那么,这种情况下,tmp指针当然就需要指向tmp.next的位置了,这部分也需要放进循环

步骤7 : 这个时候考虑循环应该用while还是for,并且考虑应该对步骤5和6使用同一套循环还是不同的一套循环

步骤8 : 因为不知道链表的长度,因此遍历的次数无从得知,所以必须用while循环

步骤9 : 由于步骤5和6考虑的是关于tmp.next.val值是否等于val后的操作,因此这算是同一件事的不同发展方向,所以放进一个循环即可,当然了,这个也跟步骤5和6需要相同的循环终止条件相关.它们的终止条件都是tmp.next=null

代码如下 :

 @Test
    public void t1() {  //单元测试方法
        int[] nums = {7,7,7,7,7,7,7,7};
        int[] nums1 = {1,2,3,6,1,4,5,7,7,8,7,9};
        ListNode head = creatLinkedList(nums1);
        showLinkedList(head);
        ListNode newHead = removeElements(head, 7);
        System.out.println();
        showLinkedList(newHead);
    }

    public ListNode creatLinkedList(int[] nums){ //创建链表方法
        if(nums == null || nums.length == 0) return null;
        ListNode head = new ListNode(nums[0]);
        ListNode tmp = head;
        for (int i = 1; i < nums.length; i++) {
            ListNode node = new ListNode(nums[i]);
            tmp.next = node;
            tmp = tmp.next;
        }
        return head;
    }

    public void showLinkedList(ListNode head){ //遍历链表方法
        while(head!= null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }

    public ListNode removeElements(ListNode head, int val) { //移除链表节点方法
        while(head!=null){
            if(head.val == val){
                head = head.next;
            }else break;
        }
        if(head == null) return head;
        ListNode tmp = head;
        while (tmp.next != null) {
            if (tmp.next.val == val) {
            tmp.next = tmp.next.next;
            } else {
            tmp = tmp.next;
            }
        }
        return head;
    }

707.设计链表

**题目 : **你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

思路 : 这题是我调试最长的一道题,自己写的代码总是有一些逻辑上的缺陷,但是我觉得这个是无法避免的,因此大量测试方法是很重要的

代码如下 :

class MyLinkedList { //单链表结构
    public void showLinkedList(ListNode head){
        while(head!= null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
    int size = 0;//链表的节点个数

    ListNode head;//头结点

    public MyLinkedList() {
        size = 0;
        ListNode head = new ListNode();
    }

    public int get(int index) {
        if(index<0||index>=size) return -1;
        if(head == null) return -1;
        ListNode tmp = head;
        int tmp_Index = 0;
        while(tmp_Index != index){
            tmp = tmp.next;
            tmp_Index++;
        }
        return tmp.val;
    }

    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);
        newHead.next = head;
        head = newHead;
        size++;
    }

    public void addAtTail(int val) {
        ListNode newTail = new ListNode(val);
        if(head == null) {
            head = newTail;
            size++;
        }
        else {
            ListNode tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newTail;
            size++;
        }
    }

    public void addAtIndex(int index, int val) {
        if(index>size||index<0) {
            return;
        }
        else if (index == 0 )addAtHead(val);
        else if(index == size){
            addAtTail(val);
        }else{
            ListNode newNode = new ListNode(val);

            int insert_Index = index-1;
            int tmp_Index = 0;
            ListNode tmp = head;
            while(tmp_Index != insert_Index){
                tmp = tmp.next;
                tmp_Index++;
            }
            newNode.next = tmp.next;
            tmp.next = newNode;
            size++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index<0||index>=size) return;
        if(index == 0) {
            head = head.next;
            return;
        }
        int tmp_Index = 0;
        ListNode tmp = head;
        while(tmp_Index != index-1){
            tmp = tmp.next;
            tmp_Index++;
        }
        tmp.next = tmp.next.next;
        size--;
    }
}

测试数据 :

	@Test
    public void t2(){
        MyLinkedList myLinkedList = new MyLinkedList();

        myLinkedList.addAtHead(1);
        showLinkedList(myLinkedList.head);
        System.out.println();

        myLinkedList.addAtTail(3);
        showLinkedList(myLinkedList.head);
        System.out.println();

        myLinkedList.addAtIndex(1,2);
        showLinkedList(myLinkedList.head);
        System.out.println();

        System.out.println(myLinkedList.get(1));

        myLinkedList.deleteAtIndex(1);
        showLinkedList(myLinkedList.head);
        System.out.println();

        System.out.println(myLinkedList.get(1));

        System.out.println(myLinkedList.get(3));

        myLinkedList.deleteAtIndex(3);
        showLinkedList(myLinkedList.head);
        System.out.println();

        myLinkedList.deleteAtIndex(0);
        showLinkedList(myLinkedList.head);
        System.out.println();

        System.out.println(myLinkedList.get(0));

        myLinkedList.deleteAtIndex(0);
        showLinkedList(myLinkedList.head);
        System.out.println();

        System.out.println(myLinkedList.get(0));


        /*myLinkedList.addAtIndex(0,20);
        showLinkedList(myLinkedList.head);
        System.out.println();
        myLinkedList.addAtIndex(1,30);
        showLinkedList(myLinkedList.head);
        System.out.println();

        System.out.println(myLinkedList.get(0));*/
        //showLinkedList(myLinkedList.head);

        /*myLinkedList.deleteAtIndex(1);
        showLinkedList(myLinkedList.head);
        System.out.println();

        System.out.println(myLinkedList.get(1));*/
        //showLinkedList(myLinkedList.head);
    }

206.反转链表

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

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

思路:

迭代 : 将指针指向倒转,但是由于没有节点保存调整后头结点的值,因此使用了一个prev指针保存

头插法 : 每次取出一个当前节点curr,插入新链表的头结点dummy.next,但是也需要调整curr.next指针指向dummy.next,这样就使得curr.next指向了curr,只是这个方式重新创建了一个链表,不是原地操作了

public ListNode reverseList(ListNode head) { // 迭代
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

public ListNode reverseList(ListNode head) { //头插法
        //if(head == null) return null;
        ListNode tmp = head;
        ListNode dummy = new ListNode();
        while(tmp!=null){
            ListNode curr = tmp;
            tmp = tmp.next;
            curr.next = dummy.next;
            dummy.next = curr;
        }
        return dummy.next;
    }

测试数据如下:

	@Test
    public void t3() {
        int[] nums = {1,2,3,4,5};
        ListNode head = creatLinkedList(nums);
        //System.out.println(head.val);
        showLinkedList(head);
        System.out.println();
        ListNode newHead = reverseList(head);
        //System.out.println(newHead.val);
        showLinkedList(newHead);
    }