代码随想录-链表

��表解题经典三板斧，哑巴节点，栈，快慢指针。哑巴节点一般是为了处理头尾节点用的，因为这边逻辑有区别，有时候会让代码变得比较长。但其实用指针+边界判断也行。这题因为逻辑简单，其实不用哑巴节点，直接用指针也行。 栈的话这题意义不大，你入栈一次不也就拿到长度了。而且对链表，pop意义不大。官方还创建了两次节点，我寻思用指针就可以了，官方这个内存消耗估计不低。 至于快慢指针，虽然少了一次常量遍历，但每次操作要操作两个指针，也快不了多少。总之就是为了解题而解题吧。但是这几个方法确实都是链表解题利器。面试的时候用上，基本题目都难不倒，跑起来不说，至少思路可以掰扯出来。 附上不用哑巴节点的方法。我感觉这题够用了

链表的定义

默认定义好，自己手撕容易忘

public class ListNode {    // 结点的值    int val;    // 下一个结点    ListNode next;    // 节点的构造函数(无参)    public ListNode() {    }    // 节点的构造函数(有一个参数)    public ListNode(int val) {        this.val = val;    }    // 节点的构造函数(有两个参数)    public ListNode(int val, ListNode next) {        this.val = val;        this.next = next;    }}

移除链表

方法一：使用虚拟节点

ListNode newHead = new ListNode(-1,head);

pre.next=cur.next;

方法二：不使用虚拟节点

记住是while不是if，可能存在连续个头节点为val

while (head != null && head.val == val) {

head = head.next;

}

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode removeElements(ListNode head, int val) {        // //使用虚拟节点        // if(head==null){        //     return head;        // }        // ListNode newHead = new ListNode(-1,head);        // ListNode pre = newHead;        // ListNode cur = head;        // while(cur!=null){        //     if(cur.val==val){        //         pre.next=cur.next;        //     }else{        //         pre=cur;        //     }        //     cur=cur.next;        // }        // return newHead.next;        //不使用虚拟节点        //记住是while不是if，可能存在连续个头节点为val        while (head != null && head.val == val) {            head = head.next;        }        if(head==null){            return head;        }        ListNode pre=head;        ListNode cur=head.next;        while(cur!=null){            if(cur.val==val){                pre.next=cur.next;            }else{                pre=cur;            }            cur=cur.next;        }        return head;    }}

设计链表

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

【高亮】先用单链表/双链表定义一个head！！！！

    int size;    ListNode head;

addAtIndex的问题//加到index-1的节点之后  //不能用while(count==index-1)  //用for  i    int size;    ListNode head;    public MyLinkedList() {    }        public int get(int index) {    }        public void addAtHead(int val) {    }        public void addAtTail(int val) {    }        public void addAtIndex(int index, int val) {    }        public void deleteAtIndex(int index) {    }}            tmp=cur.next;            cur.next=pre;            pre=cur;            cur=tmp;            if(cur==null){break;}        }            A = A != null ? A.next : headB;            B = B != null ? B.next : headA;        }        return A;