【顺序表和链表】实现增删查改数据结构 OJ题编程

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

一、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改
为什么不直接用数组：写到类里，以后就可以面向对象

1、使用顺序表MyArrayList增删查改

MyArrayList.java

import java.util.Arrays;

public class MyArrayList {

    private int[] elem;
    private static final int DEFAULT_SIZE = 10;
    private int usedSize; // 当前有效的数据个数

    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];
    }

    // 1、打印顺序表
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

    // 2、获取顺序表的有效长度
    public int size() {
        return this.usedSize;
    }

    // 判断是否需要扩容
    public boolean isFull() {
        return size() >= this.elem.length;
    }
    
    // 3、插入元素 默认在尾插
    public void add(int data) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
    
    // 4、在 pos 位置新增元素
    public void addPost(int pos, int data) {
        if(pos < 0 || pos > this.usedSize) {
            System.out.println("pos 位置不合法！");
            return;
        }

        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            // 扩容后的数组
        }

        // pos 一定是合法的
        // 向后挪
        for (int i = usedSize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data; // 插入数据
        this.usedSize++;
    }

    // 5、判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 6、查找某个元素对应的位置
    public int search(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

	// 顺序表为空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    // 7、获取 pos 位置的元素
    public int getPos(int pos) {
        if(isEmpty()) {
         	System.out.println("顺序表为空！");
            return -1;
        }
        if(pos < 0 || pos >= usedSize) {
            System.out.println("pos 位置不合法！");
            return -1; // 不考虑业务上的处理-1 后期可以抛异常
        }
        return this.elem[pos];
    }

    // 8、给 pos 位置的元素设为 value
    public void setPos(int pos, int value) {
        // 更新 pos 位置，要判断 pos 的位置
        if(pos < 0 || pos >= usedSize) {
            System.out.println("pos 位置不合法！");
            return;
        }
        if(isEmpty()) {
            System.out.println("顺序表为空！");
            return;
        }
        this.elem[pos] = value;
    }

    // 9、删除第一次出现的关键字key
    public void remove(int toRemove) {
        if(isEmpty()) {
            System.out.println("顺序表为空！");
            return;
        }
        // 可以用函数 indexOf
        int index = search(toRemove);
        if(index == -1) {
            System.out.println("没有你要删除的数!");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
        // this.elem[usedsize] = null; // 如果数组里是引用数据类型
    }

    // 10、清空顺序表
    public void clear() {
        this.usedSize = 0;
        /*
        引用类型：
        for (int i = 0; i < usedsize; i++) {
            this.elem[i] = null;
        }*/
    }

}

TestDemo.java

public class TestDemo {

    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 11);
        myArrayList.add(1, 22);
        myArrayList.add(2, 33);
        myArrayList.display(); // 11 22 33

        System.out.println(myArrayList.contains(3)); // false

        System.out.println(myArrayList.getPos(1)); // 22

        myArrayList.setPos(0, 99);
        myArrayList.display(); // 99 22 33

        myArrayList.remove(99);
        myArrayList.display(); // 22 33

        System.out.println("==================");
        myArrayList.clear();
        myArrayList.display();
    }
}

二、链表

顺序表的缺陷：
1、插入和删除元素，必须移动元素 O(N)
2、扩容- 2倍，浪费空间

能不能做到放1个，给1个空间，插入和删除不移动元素O(1)：
使用链表

为何会有这么多的数据结构：描述和组织数据的方式不一样

链表的结构非常多样，以下情况组合起来就有8种链表结构：

		单向、双向
        带头、不带头
        循环、非循环

        单向 带头 循环         双向 带头 循环
        单向 带头 非循环       双向 带头 非循环
        单向 不带头 循环       双向 不带头 循环
        *单向 不带头 非循环     *双向 不带头 非循环

1、带头 / 不带头 循环 / 非循环

2、创建链表并访问

// MylinkedList.java
class ListNode {
    public int val;
    public ListNode next;

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

public class MyLinkedList {

    // 成员变量 属于对象
    public ListNode head; // 链表的头引用

    public void creatList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        this.head = listNode1;
    }

        public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

        // 少打印一个 this.head.next != null
        /*  while(this.head != null) {
            System.out.print(this.head.val+" ");
           this.head = this.head.next;
        } */
}


// TestDemo.java
public class TestDemo {

    public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.creatList();
        myLinkedList.display();
        // 12 23 34 45 56
	}
}

3、无头单向非循环链表实现增删查改

val：数据域
next：下一个节点的地址

3.1、头插法

public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;

        // 当链表没有元素时
        /*if(this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }*/
    }

//
public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(12);
        myLinkedList.addFirst(23);
        myLinkedList.addFirst(34);
        myLinkedList.addFirst(45);
        myLinkedList.addFirst(56);
        myLinkedList.display();
        // 56 45 34 23 12 头插法 每次放在前面
    }

3.2、尾插法

public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        myLinkedList.display();
        // 12 23 34 45 56 尾插法 可与头插一起使用
    }

3.3、任意位置插入

public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("index 位置不合法！");
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        myLinkedList.display();
        // 12 23 34 45 56

        // 任意插入
        myLinkedList.addIndex(0, 99);
        myLinkedList.display(); // 99 12 23 34 45 56
        myLinkedList.addIndex(6, 99);
        myLinkedList.display(); // 99 12 23 34 45 56 99
        myLinkedList.addIndex(3, 99);
        myLinkedList.display(); // 99 12 23 99 34 45 56 99
    }

3.4、删除第一次出现关键字为key的节点

/**
 * 找到要删除的key 的前驱
*/
public ListNode searchPerv(int key) {
    ListNode cur = head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}

public void remove(int key) {
        if (this.head == null) {
            System.out.println("单链表为空，无法删除！");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }

        ListNode cur = searchPerv(key);
        if (cur == null) {
            System.out.println("没有你要删除的节点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        myLinkedList.display();

        myLinkedList.remove(12);
        myLinkedList.display(); // 删除12 --> 23 34 45 56
        myLinkedList.remove(56);
        myLinkedList.display(); // 删除56 --> 23 34 45
        myLinkedList.remove(34);
        myLinkedList.display(); // 删除34 --> 23 45
    }

3.5、删除所有值为key的节点，返回删除后链表的head --> 遍历链表一遍

【O链接】

public ListNode removeAllKey(int key) {
        if (this.head == null) return null;

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        // 头节点是key：
        if (this.head.val == key) {
            this.head = this.head.next;
        }

        return this.head;
    }

3.6、清空链表

public void clear() {
        // 粗暴方式
        // this.head = null;

        while(this.head != null) {
            ListNode curNext = head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        myLinkedList.display();

        myLinkedList.clear();
        System.out.println("xxxxxxxxx");
    }

MylinkedList.java

class ListNode {
    public int val;
    public ListNode next;

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

public class MyLinkedList {

    public ListNode head;

    public void creatList() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        this.head = listNode1;
    }

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 得到单链表的长度
    public int size() {
        int cnt = 0;
        ListNode cur = this.head;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    // 头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;

        // 当链表没有元素时
        /*if(this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }*/
    }

    // 尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }


    /**
     * 找到index-1 的位置的节点的地址
     *
     * @param index
     * @return
     */
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    // 任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("index 位置不合法！");
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }


    /**
     * 找到要删除的key 的前驱
     *
     * @param key
     * @return
     */
    public ListNode searchPerv(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    // 删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {
            System.out.println("单链表为空，无法删除！");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }

        ListNode cur = searchPerv(key);
        if (cur == null) {
            System.out.println("没有你要删除的节点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    // 删除所有值为key的节点，返回删除后链表的head --> 遍历链表一遍
    public ListNode removeAllKey(int key) {
        if (this.head == null) return null;

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        // 头节点是key：
        if (this.head.val == key) {
            this.head = this.head.next;
        }

        return this.head;
        // 删除链表中等于给定值 **val** 的所有节点。
        // [OJ链接](https://leetcode-cn.com/problems/removelinked-list-elements/description/)
    }

    public void clear() {
        // 粗暴方式
        // this.head = null;

        while(this.head != null) {
            ListNode curNext = head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }
}

// TestDemo.java
public class TestDemo {

    public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.creatList();
        myLinkedList.display();
        // 12 23 34 45 56
	}
}

4、力扣OJ

4.1、反转一个单链表

【OJ】链接

/**
* 从指定头节点开始打印
* @param newHead
*/
public void display2(ListNode newHead) {
    ListNode cur = newHead;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}
    
public ListNode reverseList() {
        if(this.head == null)  {
            return null;
        }
        ListNode prev = null;
        ListNode cur = this.head;

        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.display();

        ListNode ret = myLinkedList.reverseList();
        myLinkedList.display2(ret); // 56 45 34 23 12
}

4.2、返回链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
【OJ】链接

	// 偶数第二个
    public ListNode middleNode() {
        if(this.head == null) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 偶数第一个
    public ListNode middleNode1() {
        if(this.head == null) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            if(fast == null) {
                return slow;
            }
            slow = slow.next;
        }
        return slow;
    }

	public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.display();

        ListNode even = myLinkedList.middleNode(); // 偶数第二个
        System.out.println(even.val); // 34
        ListNode even2 = myLinkedList.middleNode1(); // 偶数第一个
        System.out.println(even2.val); // 23
        myLinkedList.addLast(56);
        ListNode odd = myLinkedList.middleNode(); // 奇数
        System.out.println(odd.val); // 34
    }

4.3、输入一个链表，输出该链表中倒数第k个结点

【OJ链接】

	public ListNode findKthToTail(int k) {
        if(k < 0 || head == null) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(k-1 != 0) {
            fast = fast.next;
            if(fast == null) {
                return null;
            }
            k--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
	
	public static void main3(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        myLinkedList.display();

        ListNode ret = myLinkedList.findKthToTail(3);
        System.out.println(ret.val); // 34
    }

4.4、合并链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
【OJ】链接

public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null) {
            tmp.next = headA;
        }
        if (headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);

        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(13);
        myLinkedList2.addLast(24);
        myLinkedList2.addLast(30);

        ListNode ret = myLinkedList.mergeTwoLists(myLinkedList.head, myLinkedList2.head);
        myLinkedList.display2(ret); // 12 13 23 24 30 34 45
    }

4.5、以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

【OJ】链接

public ListNode partition(int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val < x) {
                // 第一次
                if(bs == null) {
                    bs = cur;
                    be = cur;
                }else {
                    // 非首次
                    be.next = cur;
                    be = be.next;
                }
            }else {
                // 第一次
                if(as == null) {
                    as = cur;
                    ae = cur;
                }else {
                    // 非首次
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        // 预防第一个段为空
        if(bs == null) {
            return as;
        }
        // 串
        be.next = as;
        // 预防第二个段中的数据 最后一个节点不是空
        if(as != null) {
            ae.next = null;
        }

        return bs;
    }

4.6、删除链表重复节点

【OJ】链接

public ListNode deleteDuplication() {
        ListNode cur = head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(cur != null) {
            if(cur.next != null && cur.val == cur.next.val) {
                while(cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        // 防止最后一个节点也是重复 将最后一个不重复的节点置为空
        tmp.next = null;
        return newHead.next;
    }

MylinkedList.java

class ListNode {
    public int val;
    public ListNode next;

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

public class MyLinkedList {

    public ListNode head;

    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 从指定头节点开始打印
     * @param newHead
     */
    public void display2(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }


    // 反转一个单链表
    public ListNode reverseList() {
        if(this.head == null)  {
            return null;
        }
        ListNode prev = null;
        ListNode cur = this.head;

        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    //  给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
    // 偶数第二个
    public ListNode middleNode() {
        if(this.head == null) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 偶数第一个
    public ListNode middleNode1() {
        if(this.head == null) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            if(fast == null) {
                return slow;
            }
            slow = slow.next;
        }
        return slow;
    }

    // 输入一个链表，输出该链表中倒数第k个结点
    public ListNode findKthToTail(int k) {
        if(k < 0 || head == null) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(k-1 != 0) {
            fast = fast.next;
            if(fast == null) {
                return null;
            }
            k--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    // 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null) {
            tmp.next = headA;
        }
        if (headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }

    // 以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
    public ListNode partition(int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.val < x) {
                // 第一次
                if(bs == null) {
                    bs = cur;
                    be = cur;
                }else {
                    // 非首次
                    be.next = cur;
                    be = be.next;
                }
            }else {
                // 第一次
                if(as == null) {
                    as = cur;
                    ae = cur;
                }else {
                    // 非首次
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        // 预防第一个段为空
        if(bs == null) {
            return as;
        }
        // 串
        be.next = as;
        // 预防第二个段中的数据 最后一个节点不是空
        if(as != null) {
            ae.next = null;
        }

        return bs;
    }

    // 删除链表重复节点
    public ListNode deleteDuplication() {
        ListNode cur = head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(cur != null) {
            if(cur.next != null && cur.val == cur.next.val) {
                while(cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        // 防止最后一个节点也是重复 将最后一个不重复的节点置为空
        tmp.next = null;
        return newHead.next;
    }
}

TestDemo.java

public class TestDemo {

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);

        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(13);
        myLinkedList2.addLast(24);
        myLinkedList2.addLast(30);

        ListNode ret = myLinkedList.mergeTwoLists(myLinkedList.head, myLinkedList2.head);
        myLinkedList.display2(ret); // 12 13 23 24 30 34 45
    }

    public static void main3(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);
        myLinkedList.display();

        ListNode ret = myLinkedList.findKthToTail(3);
        System.out.println(ret.val); // 34
    }

    public static void main2(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.display();

        ListNode even = myLinkedList.middleNode(); // 偶数第二个
        System.out.println(even.val); // 34
        ListNode even2 = myLinkedList.middleNode1(); // 偶数第一个
        System.out.println(even2.val); // 23
        myLinkedList.addLast(56);
        ListNode odd = myLinkedList.middleNode(); // 奇数
        System.out.println(odd.val); // 34
    }

    public static void main1(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.display();

        ListNode ret = myLinkedList.reverseList();
        myLinkedList.display2(ret); // 56 45 34 23 12
    }
}

4.7、链表的回文结构

【OJ链接】

public boolean chkPalindrome() {
        if(head == null) return true;
        // 找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // slow走到了中间位置
        // 反转
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next; // 记录cur下一个
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 判断回文
        while(head != slow) {
            if(head.val != slow.val) {
                return false;
            }
            // 偶数
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(23);
        myLinkedList.addLast(12);

        System.out.println(myLinkedList.chkPalindrome()); // true
    }

4.8、输入两个链表，找出它们的第一个公共结点

【OJ链接】

	// 创建相交链表 测试
    public void createCut(ListNode headA, ListNode headB) {
        headA.next.next = headB.next.next;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        // pl==null
        pl = headA;
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        // ps = null
        ps = headB;
        int len = lenA - lenB; // 差值步
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        // pl永远指向了最长的链表 ps永远指向了最短的链表 求了差值步len

        // 较长的链表 pl 走差值步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        // 同时走 直到相遇
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        return pl; // 如果为空 直接返回就可
    }

public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);

        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addLast(13);
        myLinkedList1.addLast(23);
        myLinkedList1.addLast(30);

        myLinkedList.createCut(myLinkedList.head, myLinkedList1.head);
        ListNode ret = myLinkedList.getIntersectionNode(myLinkedList.head, myLinkedList1.head);
        System.out.println(ret.val); // 30
    }

4.9、给定一个链表，判断链表中，是否有环

【OJ链接】

	public boolean hasCycle() {
        if(head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast .next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

    public boolean hasCycle2() {
        if(head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast .next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return false;
        }
        return true;
    }

	// 构建一个环
    public void creatLoop() {
        ListNode cur = this.head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = head.next.next;
    }


public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(23);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addLast(56);

        myLinkedList.creatLoop();
        System.out.println(myLinkedList.hasCycle()); // true
    }

4.10、给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

【OJ链接】

	public ListNode detectCycle() {
        // 判断是否有环
        if(head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast .next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        // 返回入口点
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

4.11、选择题

5、无头双向链表增删查改

MylinkedList.java

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

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

public class MyLinkedList {

    public ListNode head; // 指向双向链表的头节点
    public ListNode last; // 指向的是尾巴节点

    public void display() {
        // 和单链表的打印方式是一样的
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 得到单链表的长度
    public int size() {
        int cnt = 0;
        ListNode cur = this.head;
        while(cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    // 查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
            this.last = node;
        }else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

    // 尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null) {
            head = node;
            last = node;
        }else {
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }
    }


    public ListNode searchIndex(int index) {
        // 返回index位置的地址
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    // 任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        if(index < 0 || index > size()) {
            System.out.println("index 位置不合法");
            return;
        }
        // 头插
        if(index == 0) {
            addFirst(data);
            return;
        }
        // 尾插
        if(index == size()) {
            addLast(data);
            return;
        }
        // 中间
        ListNode cur = searchIndex(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
    }

    // 删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == this.head) {
                    this.head = head.next;
                    if(this.head != null) { //
                        this.head.prev = null;
                    }else {
                        this.last = null;
                    }
                }else if(cur == this.last){
                    this.last = this.last.prev;
                    this.last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                return;
            }
            cur = cur.next;
        }
    }

    public void remove1(int key){
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == this.head) {
                    this.head = head.next;
                    if(this.head != null) { //
                        this.head.prev = null;
                    }else {
                        this.last = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        // 中间位置
                        cur.next.prev = cur.prev;
                    }else {
                        this.last = this.last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    // 删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == this.head) {
                    this.head = head.next;
                    if(this.head != null) { //
                        this.head.prev = null;
                    }else {
                        this.last = null;
                    }
                }else if(cur == this.last){
                    this.last = this.last.prev;
                    this.last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                // return;
            }
            cur = cur.next;
        }
    }

    public void clear() {
        while(this.head != null) {
            ListNode curNext = this.head.next;
            this.head.next = null;
            this.head.prev = null;
            this.head = curNext;
        }
        this.last = null;

        /*ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
        this.last = null;*/
    }
}

TestDemo.java

public class TestDemo {

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(2);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.display(); // 1 2 2 2 3

        myLinkedList.remove(1);
        myLinkedList.display(); // 2 2 2 3

        // myLinkedList.removeAllKey(2);
        // myLinkedList.display(); // 3

        myLinkedList.addIndex(0, 99);
        myLinkedList.display(); // 99 2 2 2 3
        myLinkedList.addIndex(5, 99);
        myLinkedList.display(); // 99 2 2 2 3 99
        myLinkedList.addIndex(3, 99);
        myLinkedList.display(); // 99 2 2 99 2 3 99
    }

    public static void main1(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(1);
        myLinkedList.addFirst(2);
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(4);

        System.out.println(myLinkedList.size()); // 4
        System.out.println(myLinkedList.contains(1)); // true
        myLinkedList.display(); // 4 3 2 1

        myLinkedList.addLast(11);
        myLinkedList.addLast(12);
        myLinkedList.display(); // 4 3 2 1 11 12
    }
}

6、实现双向链表（带傀儡节点）

MylinkedList.java

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

public class MyLinkedList {
    public ListNode head = new ListNode(-1);
    public ListNode last;

    // 打印
    public void display() {
        ListNode cur = this.head.next; //
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 得到单链表的长度
    public int size() {
        ListNode cur = this.head.next; //
        int cnt = 0;
        while(cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    // 查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head.next;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head.next == null) {
            this.head.next = node;
            node.prev = this.head;
            this.last = node;
        } else {
            node.next = this.head.next;
            node.next.prev = node;
            node.prev = this.head;
            this.head.next = node;
        }
    }

    // 尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head.next == null) {
            this.head.next = node;
            node.prev = this.head;
            this.last = node;
        } else {
            this.last.next = node;
            node.prev = last;
            this.last = node;
        }
    }

    public ListNode searchIndex(int index) {
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    // 任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index < 0 || index > size()) {
            System.out.println("index 下标范围错误");
            return;
        }
        if(index == 0) {
            addFirst(data);
        } else if(index == size()) {
            addLast(data);
        } else {
            ListNode node = new ListNode(data);
            ListNode cur = searchIndex(index);
            node.next = cur;
            node.prev = cur.prev;
            cur.prev.next = node;
            cur.prev = node;
        }
    }

    // 删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = this.head.next;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == this.head.next) {
                    this.head.next = cur.next;
                    cur.next.prev = this.head;
                } else if (cur == this.last) {
                    this.last = this.last.prev;
                    this.last.next = null;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                return;
            }
            cur = cur.next;
        }
    }

    // 删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = this.head.next;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == this.head.next) {
                    this.head.next = cur.next;
                    cur.next.prev = this.head;
                } else if (cur == this.last) {
                    this.last = this.last.prev;
                    this.last.next = null;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }
    }

    // 清空
    public void clear() {
        ListNode cur = this.head.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
        this.last = null;
    }
}

三、总结

问题：
1.顺序表和链表的区别？
2.数组和链表的区别？
3.ArrayList和LinkedList的区别？

共同点：对数据的组织方式和描述方法不同

组织：
1.顺序表底层是一个数组，逻辑上和物理上都是连续的
2.链表是一个由若干节点组成的数据结构，逻辑上是连续的，但在物理上/内存上 不一定连续
操作:
1.顺序表适合查找相关的操作，因为可以使用下标，直接获取到某个位置的元素
2.链表适合频繁地插入和删除操作，不需要像顺序表一样移动元素。链表的插入，只需要修改指向
3.顺序表满了需要扩容，扩容后不一定都能放完，所以空间上的利用率不高