(相关资料图)

链表

• 定义:通过指针串联在一起的线性结构，每一个节点由两个部分组成：数据域和指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null，即为空指针。

链表类型

1. 单链表，见上图2. 双链表

3. 循环链表，即链表首尾相连，可以解决约瑟夫环问题

链表的存储方式

数组在内存中是连续分布的，但是链表在内存中不是连续分布的

链表的定义

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;    }}

链表的插入、删除与查询

移除链表元素（力扣203.）

1. 有虚拟节点方式；记得head为val值的边缘条件，以及target指针的空指针问题

/** * 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) {        ListNode low = new ListNode();        low.next = head;        ListNode target = head;        if(head == null){            return null;        }        while(head.val == val){            head = head.next;            if(head==null){                return head;            }        }        while(target != null){            while(target.val == val){                low.next = target.next;                target = target.next;                if(target == null){                    return head;                }            }            low = low.next;            if(target!=null){            target = target.next;}        }        return head;    }}

2. 无虚拟节点方式；先对head指向的值处理，在运行到非val值后扫描后指针

/**无虚拟节点方式；先对head指向的值处理，在运行到非val值后扫描后指针 */class Solution {    public ListNode removeElements(ListNode head, int val) {       //先将head指针处理至不为val值的地方       while(head != null && head.val == val){           head = head.next;       }       //head为空，则直接返回       if(head == null){           return head;       }        ListNode pre = head;        ListNode post = head.next;        while(post != null){            if(post.val == val){                pre.next = post.next;            }else{                pre = post;            }            post = post.next;        }        return head;    }}

设计链表：实现五个函数（力扣707.）

获取第n个节点的数值

• 使用虚拟头结点的方式 dummynode
• while(n)
• cur = cur.next;
• n--

头部插入节点

• new一个新node
• newNode.next=dummyHead.next;(注意顺序)
• dummyhead.next=newNode;
• size++；

尾部插入节点

• cur = dummyhead；
• while(cur.next == null)
• cur = cur.next;
• cur.next = newNode

第n个节点的插入

• cur应该指向第n个节点的前一个结点
• cur = dummyhead
• while(n)
• cur = cur.next;
• n--;
• newNode.next=cur.next;
• cur.next=newNode;
• size++;

第n个节点的删除

• 判断n的合法性
• cur= dummyhead;
• while(n)
• cur = cur.next;
• n--;
• cur.next=cur.next.next;
• return dummyhead.next;

class ListNode{    int val;    ListNode next;    ListNode(){}    ListNode(int val){        this.val = val;    }}class MyLinkedList {//带有头结点的链表    //容量大小    int size;    //虚拟头结点    ListNode dummyhead;    public MyLinkedList() {        //初始化单链表        size = 0;        dummyhead = new ListNode(0);    }        public int get(int index) {        if(index < 0 || index >= size){            return -1;        }        ListNode current = dummyhead;        while(index >= 0){            current = current.next;            index --;        }        return current.val;    }        public void addAtHead(int val) {        ListNode current = dummyhead;        ListNode target = new ListNode(val);        target.next = current.next;        current.next = target;        size++;    }        public void addAtTail(int val) {        ListNode current = dummyhead;        while(current.next != null){            current = current.next;        }        ListNode target = new ListNode(val);        target.next = null;        current.next = target;        size++;    }        public void addAtIndex(int index, int val) {        if(index < 0 || index >= size + 1){            return;        }        ListNode current = dummyhead;        while(index > 0){            current = current.next;            index--;        }        ListNode target = new ListNode(val);        target.next = current.next;        current.next = target;        size++;    }        public void deleteAtIndex(int index) {        if(index < 0 || index >= size){            return;        }        ListNode current = dummyhead;        while(index > 0){            current = current.next;            index--;        }        current.next = current.next.next;        size--;    }}/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */

反转链表（力扣206.）

• 遍历数组＋头插法

/** * 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 reverseList(ListNode head) {        // ListNode pummyhead = new ListNode();        // pummyhead.next = head;        if(head == null){            return null;        }        ListNode from = head.next;        ListNode targetPummyHead = new ListNode();        ListNode current = targetPummyHead;        while(head != null){            head.next = targetPummyHead.next;            targetPummyHead.next = head;            head = from;            if(from != null){                from = from.next;            }else{from = null;}        }        return targetPummyHead.next;    }}

• 双指针写法

1. 初始化：cur = head;pre=null;
2. 遍历链表：while(cur != null)
3. 需要一个临时指针temp = cur.next
4. cur.next=pre;
5. pre=cur;
6. cur=temp
7. return pre;

class Solution {    public ListNode reverseList(ListNode head) {       //双指针思路       //初始化       ListNode pre = null;       ListNode cur = head;       while( cur != null){           ListNode temp = cur.next;           cur.next = pre;           pre = cur;           cur = temp;       }       return pre;    }}

• 递归算法

1. reverse(cur,pre){
2. if(cur == null)return pre;//此时终止
3. temp = cur.next;
4. cur.next=pre;
5. reverse(temp,cur)}
6. //使用：return reverse（head,null);

其实内核解法与双指针解法相同

class Solution {    public ListNode reverseList(ListNode head) {        return reverse(null,head);    }    public ListNode reverse(ListNode pre,ListNode current){        if(current == null){            return pre;//递归的终止条件为current为null        }        ListNode temp = current.next;//临时节点暂存        current.next = pre;        return reverse(current,temp);    }}