【順序表和鏈表】實作增刪查改資料結構 OJ題編程-有解無憂

線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列，線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤

一、順序表

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改
為什么不直接用陣列：寫到類里，以后就可以面向物件

1、使用順序表MyArrayList增刪查改

MyArrayList.java

import java.util.Arrays;

public class MyArrayList {

    public int[] elem;
    public int usedsize; // 當前有效的資料個數

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

    // 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 this.usedsize == this.elem.length;
    }

    // 3、在 pos 位置新增元素
    public void add(int pos, int data) {
        if(pos < 0 || pos > usedsize) {
            System.out.println("pos 位置不合法！");
            return;
        }

        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            // 擴容后的陣列
        }

        for (int i = usedsize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedsize++;
    }

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

    // 5、查找某個元素對應的位置
    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;
    }

    // 6、獲取 pos 位置的元素
    public int getPos(int pos) {
        if(pos < 0 || pos >= usedsize) {
            System.out.println("pos 位置不合法！");
            return -1; // 不考慮業務上的處理-1 后期可以拋例外
        }
        if(isEmpty()) {
            System.out.println("順序表為空！");
            return -1;
        }
        return this.elem[pos];
    }

    // 7、給 pos 位置的元素設為 value
    public void setPos(int pos, int value) {
        if(pos < 0 || pos >= usedsize) {
            System.out.println("pos 位置不合法！");
            return;
        }
        if(isEmpty()) {
            System.out.println("順序表為空！");
            return;
        }
        this.elem[pos] = value;
    }

    // 8、洗掉第一次出現的關鍵字key
    public void remove(int toRemove) {
        if(isEmpty()) {
            System.out.println("順序表為空！");
            return;
        }
        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; // 如果陣列里是參考資料型別
    }

    // 9、清空順序表
    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
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352221.html

標籤：其他

上一篇：【圖解資料結構】堆 - 基本功能實作、向上調整、向下調整演算法

下一篇：資料結構與演算法之時間復雜度與空間復雜度

【順序表和鏈表】實作增刪查改資料結構 OJ題編程

線性表

一、順序表

1、使用順序表MyArrayList增刪查改

MyArrayList.java

TestDemo.java

二、鏈表

1、帶頭 / 不帶頭 回圈 / 非回圈

2、創建鏈表并訪問

3、無頭單向非回圈鏈表實作增刪查改

3.1、頭插法

3.2、尾插法

3.3、任意位置插入

3.4、洗掉第一次出現關鍵字為key的節點

3.5、洗掉所有值為key的節點，回傳洗掉后鏈表的head --> 遍歷鏈表一遍

3.6、清空鏈表

MylinkedList.java

4、力扣OJ

4.1、反轉一個單鏈表

4.2、回傳鏈表的中間結點

4.3、輸入一個鏈表，輸出該鏈表中倒數第k個結點

4.4、合并鏈表

4.5、以給定值x為基準將鏈表分割成兩部分，所有小于x的結點排在大于或等于x的結點之前

4.6、洗掉鏈表重復節點

MylinkedList.java

TestDemo.java

1、帶頭 / 不帶頭回圈 / 非回圈