当前位置:   article > 正文

java数据结构 --- 链表

java数据结构 --- 链表


顺序表适合查找操作,不适合频繁的插入和删除操作
链表的分类可以根据单向或者双向,是否循环,有无头节点,共有2^3,及8种
链表在逻辑上连续,在物理上不连续

1. 初识链表(不带头节点的单向非循环链表)

1.1 链表的创建

public class LinkList {
    class Link{
        int val;
        Link add;
        public Link(int val){
            this.val = val;
        }
    }
    //头节点
    Link link;
    public void creat(){
       Link link1 = new Link(45);
       Link link2 = new Link(49);
       Link link3 = new Link(89);
       Link link4 = new Link(60);
       Link link5 = new Link(90);

        this.link = link1;
        link1.add = link2;
        link2.add = link3;
        link3.add = link4;
        link4.add = link5;
        link5.add = null;
    }
    public static void main(String[] args) {
        LinkList linklist = new LinkList();
        linklist.creat();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

1.2 链表的功能实现

    public void display(){
    //保持头节点位置不变,定义一个头结点的傀儡,代替头节点跑腿
       Link re = this.link;
      //判断re是否为空
       while(re!= null){
           System.out.print(re.val + " ");
           //使re指向下一个结点
           re = re.add;
       }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

需要注意遍历链表时while函数括号中并不是(re.next != null),而是(re != null).

1.2.1 遍历链表

    public int size(){
        Link re = this.link;
        int i = 0;
        while(re != null){
            i++;
            re = re.add;
        }
        return i;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

1.2.2 判断链表中是否包含某元素

    public boolean contions(int n){
        Link re = this.link;
        while(re != null){
            if (n == re.val){
                return true;
            }
            re = re.add;
        }
        return false;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

1.2.3 头插法

    public void addFirst(int data){
        Link add = new Link(data);
        add.add = this.link;
        link = add;
    }
  • 1
  • 2
  • 3
  • 4
  • 5

1.2.4 尾插法

    public void addLast(int data){
        Link re = this.link;
        Link add = new Link(data);
        if(re == null){
            this.link = add;
        }else{
            while(re.add != null){
                re = re.add;
            }
            re.add = add;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

1.2.5 任意下标插入

    public void addIndex(int index, int date){
        if (index < 0 | index > size() - 1){
            new IndexwrongException("任意下标插入异常");
        }
        if (index == 0){
            addFirst(date);
            return;
        }
        if(index == size() - 1){
            addLast(date);
            return;
        }
        Link add = new Link(date);
        Link re = this.link;
        int i = 0;
        while(i < index - 1){
            re = re.add;
            i++;
        }
        add.add = re.add;
        re.add = add;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

1.2.6 删除元素

public void remove(int date){
        if (link == null){
            return ;
        }
        if(this.link.val == date){
            this.link = this.link.add;
            return;
        }
        Link rem = find(date);
        if(rem == null){
            System.out.println("没有该元素");
        }else{
            rem.add = rem.add.add;
        }
    }
    private Link find(int date){
        Link re = this.link;
        while(re.add != null){
            if (re.add.val == date){
                return re;
            }
            re = re.add;
        }
        return null;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25


在这里插入图片描述



1.2.7 删除的数字有多个且要全部删除

    public void removeAllKey(int date){
        if (node == null){
            return ;
        }
        Node re1 = node;
        Node re2 = node.next;
        while(re2 != null){
            if(re2.val == date){
                re1.next = re2.next;
                re2 = re2.next;
            }else{
                re1 = re2;
                re2 = re2.next;
            }
        }
        if (node.val == date){
            node = node.next;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

注意最后的if函数中不要写成node = re1,因为re1不一定是node.next

1.3 二刷链表代码

package danlianbiao;

class LinkedList{
    static class Node{
        int valu = 0;
        Node next = null;
        public Node(int valu){
            this.valu = valu;
        }
    }
    Node node0 = null;
    int size = 0;
    void creatList(){
        Node node1 = new Node(99);
        Node node2 = new Node(89);
        Node node3 = new Node(67);
        Node node4 = new Node(34);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node0 = node1;
        this.size = 4;
    }
    void display(){
        Node eg = this.node0;
        while(eg != null){
            System.out.print(eg.valu + "  ");
            eg = eg.next;
        }
        System.out.println();
    }
    void headadd (int val){
        Node node = new Node(val);
        node.next = node0;
        node0 = node;
        this.size++;
    }
    void tailadd(int val){
        Node node = new Node(val);
        Node eg = this.node0;
        if(this.size != 0){
            while(eg.next != null){
                eg = eg.next;
            }
            eg.next = node;
        }else{
            this.node0 = node;
        }
        this.size++;
    }
    void add ( int pos, int val) throws IllegalLocation{
        if (pos < 0 || pos >this.size){
            throw new IllegalLocation("pos位置不合法");
        }else if(pos == 0){
            headadd(val);
        }else if (pos == this.size){
            tailadd(val);
        }else{
            Node node = new Node(val);
            Node eg = this.node0;
            while(pos - 1 != 0){
                eg = eg.next;
                pos--;
            }
            node.next = eg.next;
            eg.next = node;
            this.size++;
        }
    }
    boolean contain(int val){
        Node eg = this.node0;
        while(eg != null){
            if(eg.valu == val)
                return true;
            eg = eg.next;
        }
        return false;
    }
    void remove(int val){
        if(this.node0 == null){
            System.out.println("删除失败, 此链表为空");
            return;
        }
        Node eg = this.node0;
//          if(eg.valu == val){
//              eg = eg.next;
//              this.size--;
//              return;
//        }
//注意:删除的元素为链表中第一个元素时,不能用eg操作,用node0;
        if(this.node0.valu == val){
            this.node0 = this.node0.next;
            this.size--;
            return;
        }
        while(eg.next != null){
            if (eg.next.valu == val){
                eg.next = eg.next.next;
                this.size--;
                return;
            }
            eg = eg.next;
        }
        System.out.println("删除失败,链表中没有该元素");
    }
    void removeall(int val){
        if (this.size == 0){
            System.out.println("删除失败,该链表为空");
            return;
        }
        Node eg1 = this.node0;
        Node eg2 = this.node0.next;
        while(eg2 != null){
            if (eg2.valu == val){
                eg1.next = eg2.next;
                eg2 = eg2.next;
                this.size--;
            }else{
                eg1 = eg2;
                eg2 = eg2.next;
            }
        }
        if(this.node0.valu == val){
            node0 = node0.next;
            this.size--;
        }
    }
    void clean(){
        this.node0 = null;
        this.size = 0;
    }
}



public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.creatList();
        //System.out.println("size = " + list.size);
        list.headadd(100);
        list.display();
        list.headadd(100);
        list.tailadd(100);
        list.tailadd(46);
        list.display();
        //System.out.println("size = " + list.size);
        try{
            list.add(0, 100);
            //System.out.println("size = " + list.size);
            list.add(9, 340);
            //System.out.println("size = " + list.size);
            list.add(10,78 );
            //System.out.println("size = " + list.size);
            list.add(4, 100);
            System.out.println("size = " + list.size);
        }catch(IllegalLocation e){
            e.printStackTrace();
        }
        list.display();
        list.remove(450);
        list.display();
        list.remove(78);
        list.display();
        list.remove(100);
        list.display();
        list.remove(1000);
        System.out.println("size = " + list.size);
        list.removeall(100);
        list.display();
        System.out.println("size = " + list.size);
        System.out.println(list.contain(100));
        System.out.println(list.contain(1000));
        //list.disList();
        list.clean();
        list.display();
        System.out.print("size = " + list.size);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179

在这里插入图片描述

2. 链表题目

2.1 旋转链表(置换链表)

//置换单链表
    Node disList(){
        if(this.node0 == null){
            return null;
        }else if (this.node0.next == null){
            return this.node0;
        }else{
            Node eg1 = this.node0.next;
            this.size = 1;
            this.node0.next = null;
            while(eg1 != null){
                Node eg2 = eg1.next;
                headadd(eg1.valu);
                eg1 = eg2;
            }
        }
        return this.node0;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

2.2 获取链表中间节点(快慢指针)

    //获取链表中间元素
    Node getmidlist(){
        if (this.node0 == null){
            System.out.println("获取失败,该线性表为空");
            return null;
        }else if (this.size == 1){
            System.out.println("获取成功,该线性表只有一个元素");
            return this.node0;
        }else{
            Node fast = this.node0;
            Node slow = this.node0;
            while((fast != null) && (fast.next != null)){
            //注意这里必须先是fast!=null在前,否则可能会空指针异常
                fast = fast.next.next;
                slow = slow;
            }
            return slow;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

2.3 获取倒数第k个节点

    //获取倒数第k个节点
    Node getbackwards(int k){
        if ((k <= 0)){
            System.out.println("获取失败, 要获取位置不合法");
            return null;
        }
        if (this.node0 == null){
            System.out.println("获取失败,链表为空");
        }
        Node fast = this.node0;
        Node slow = this.node0;
        while (fast.next != null){
            while(k - 1 != 0){
                fast = fast.next;
                k--;
                if (fast.next == null){
                    System.out.println("获取失败, 要获取位置不合法");
                    return null;
                }
            }
            slow = slow.next;
            fast = fast.next;
        }
        System.out.println("获取成功");
        return slow;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

2.4 有序合并两个有序链表

    Node mergelists(Node node1, Node node2){
        Node newnode = new Node(0);
        Node eg = newnode;
        while((node1 != null) && (node2 != null)){
            if (node1.valu < node2.valu){
                eg.next = node1;
                node1 = node1.next;
                eg = eg.next;

            }else{
                eg.next = node2;
                node2 = node2.next;
                eg = eg.next;
            }
        }
        if (node1 != null){
            eg.next = node1;
        }else{
            eg.next = node2;
        }
        return newnode.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

2.5 链表分割 (血的教训)

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
在这里插入图片描述

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if (pHead == null) {
            return null;
        }
        ListNode eg = pHead;
        ListNode ea1 = null;
        ListNode es1 = null;
        ListNode ea2 = null;
        ListNode es2 = null;
        while (eg != null) {
            if (eg.val < x) {
                if (ea1 == null) {
                    ea1 = eg;
                    es1 = eg;
                } else {
                    es1.next = eg;
                    es1 = es1.next;
                }
                eg = eg.next;
            } else {
                if (ea2 == null) {
                    ea2 = eg;
                    es2 = eg;
                } else {
                    es2.next = eg;
                    es2 = es2.next;
                }
                eg = eg.next;
            }
        }
        if (ea1 == null) {
            return ea2;
        }
        es1.next = ea2;
        if (ea2 != null) {
            es2.next = null;
        }
        return ea1;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

这道题值得注意的细节在于在执行es2.next = null;之前必须判断ea2是不是为空,否则可能会报空指针异常
血的教训

2.6 链表指定区间反转(遍历一次)

一下午的心血
在这里插入图片描述

    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        if (m == n) {
            return head;
        }
        ListNode eg = head;
        for (int i = 1; i < m - 1; i++) {
            eg = eg.next;
        }
        ListNode eg1 = null;
        if(head.next.next == null){
            eg1 = eg.next;
            eg.next = null;
            eg1.next = eg;
            head = eg1;
            return head;
        }
        if(m == 1){
            eg1 = eg;
        }else{
           eg1 = eg.next;
        }
        ListNode eg2 = eg1.next;
        ListNode eg4 = eg1;
        eg.next = null;
        eg1.next = null;
        while ((n - m) != 0) {
            ListNode eg3 = eg2.next;
            eg2.next = eg1;
            eg1 = eg2;
            eg2 = eg3;
            n--;

        }
        if (m == 1){
            eg4.next = eg2;
            return eg1;
        }
        eg4.next = eg2;
        eg.next = eg1;
        return head;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

2.7 判断回文链表

在这里插入图片描述

需要注意的点在于
在这里插入图片描述

注意这里判断条件不能写成slow.next != null,而是eg1.next ! null

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        //找中间节点
        if (A == null){
            return false;
        }
        if(A.next == null){
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        while((fast != null) && (fast.next != null)){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode eg1 = slow.next;
        while(eg1 != null){
        //注意这里判断条件不能写成slow.next != null;
            ListNode eg2 = eg1.next;
            eg1.next = slow;
            slow = eg1;
            eg1 = eg2;
        }
        ListNode eg3 = A;
        while(eg3 != slow){
            if(eg3.val != slow.val){
                return false;
            }
            if (eg3.next == slow){
                return true;
            }
            eg3 = eg3.next;
            slow = slow.next;
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

2.8 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     if(headA == null || headB == null){
         return null;
     }
     ListNode eg1 = headA;
     ListNode eg2 = headB;
    while(eg1 != eg2){
    eg1 = (eg1 == null)? headB: eg1.next;
    eg2 = (eg2 == null)? headA: eg2.next;
     }
     return eg1;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

2.9 判断是否有环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

2.10 链表中的节点每k个一组翻转

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if (head == null){
            return null;
        }
        //len记录链表长度
        int len = 0;
        //eg用于遍历链表
        ListNode eg = head;
        while (eg != null){
             len++;
             eg = eg.next;
        }
        if (len < k){
        //如果长度小于k,返回当前链表
            return head;
        }
        int num = len / k;
        //ListNode用于标记每一组的第一个节点
        ListNode headeg = head;
        //eg用于记录每一组翻转后的最后一个节点
        eg = head;
        for (int i = 1; i <= num; i++){
        //为每一组的翻转做准备工作
            ListNode eg0 = headeg;
            ListNode eg1 = headeg.next;
            headeg.next = null;
            int egi = k;
            while(egi - 1!= 0){
            //对每一组进行翻转
                egi--;
                ListNode eg2 = eg1.next;
                eg1.next = headeg;
                headeg = eg1;
                eg1 = eg2;
            }
            if (i == 1){
   //移动头节点,使其指向翻转后的第一个节点,只能在第一次翻转时执行一次
                head = headeg;
            }else{
       //连接翻转后的前一组与翻转后的当前组
                eg.next = headeg;
                eg = eg0;
            }
            //连接翻转后的当前组与下一组
            eg0.next = eg1;
            //使headeg始终指向下一组的头节点
            headeg = eg1;
        }
       return head;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

2.11 链表中环的入口结点

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null){
            return null;
        }
        ListNode fast = pHead, slow = pHead;
        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;
        }
        slow = pHead;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/687140
推荐阅读
相关标签
  

闽ICP备14008679号