Java中的链表

前言

上一节中，我们讲过了Java中的ArrayList，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

一、链表

1.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序来实现的。类似于火车一样。

注意：

1. 链式结构在逻辑上是连续的，但是在物理上不一定连续
2. 现实中的结点一般都是在堆上申请出来的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

实际中，链表的结构多种多样，一下情况组合起来就有8种链表结构：

1. 单向或者双向
   

2. 带头或者不带头
   

3. 循环或者非循环
   

虽然有这么多的链表结构，但是我们重点讲解两种：

• 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
• 无头双向链表：在java集合框架中LinkedList底层实现就是无头双向循环链表。

1.2 链表的实现

SingleLinkedList类

// 1、无头单向非循环链表实现
public class SingleLinkedList {

    class Node {
        public int val;
        public Node next;

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

    public Node head;

    public void createLinkList() {
        Node node1 = new Node(12);
        Node node2 = new Node(45);
        Node node3 = new Node(88);
        Node node4 = new Node(92);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }

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

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

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

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

    //尾插法
    public void addLast(int data) {
        Node node = new Node(data);

        if (head == null) {
            head = node;
        }

        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) throws ListIndexOutofException {
        if (index < 0 || index > size()) {
            throw new ListIndexOutofException("index位置不合法");
        }
        if (index == 0) {
            addFirst(data);
        }
        if (index == size()) {
            addLast(data);
        }

        int count = 0;
        Node cur = head;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }

        Node node = new Node(data);
        node.next = cur.next;
        cur.next = node;

    }



    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchprev(key);
        if(cur == null) {
            return;
        }
        Node del = cur.next; //要删除的节点
        cur.next = del.next;
    }

    /*
    查找key前一个节点
     */
    private Node searchprev(int key) {
        Node cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null; //没有删除的节点
    }

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

    public void clear() {
        head = null;
    }
}

ListIndexOutofException类

public class ListIndexOutofException extends RuntimeException {
    public ListIndexOutofException() {
    }

    public ListIndexOutofException(String message) {
        super(message);
    }
}

Test类

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.createLinkList();
        singleLinkedList.display();
        System.out.println(singleLinkedList.contains(12));
        System.out.println(singleLinkedList.size());

        singleLinkedList.addFirst(8); //头插
        singleLinkedList.display();

        singleLinkedList.addLast(9);//尾插
        singleLinkedList.display();

        singleLinkedList.addIndex(2,999);
        singleLinkedList.addIndex(4,999);
        singleLinkedList.display();

        singleLinkedList.remove(88);
        singleLinkedList.display();

        singleLinkedList.removeAllKey(999);
        singleLinkedList.display();
    }
}

二、链表面试题

以下是我要讲解的5个关于链表的面试题，包含OJ链接。

2.1 判定链表是否是回文

题目：链表的回文结构

思路： 由于链表是单向的，所以我们如果要使用双指针的思想解决该题，就需要将后半部分数据的指向进行逆置。也就是

	1——>2——>2<——1

要实现后半部分的逆置，我们需要找到链表的中间节点 。在链表的实现里，我们已经使用快慢指针找到链表的中间节点。最后我们再使用双指针，遍历链表，比较前后对称节点的值是否相等。

代码实现：

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if(head == null) {
            return false;
        }
        if(head.next == null) {
            return true;
        }
        //快慢指针找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //翻转后半部分的指向
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        while(slow != head) {
            if(slow.val != head.val) {
                return false;
            }
            //下面这个if语句是用来判断链表长度为偶数的情况的
            if(head.next == slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;

    }
}

2.2 合并两个有序链表

题目：合并两个有序链表

思路： 要返回一个新的升序链表，那么我们需要申请一个新的头节点，然后通过遍历两个链表，并将其值进行对比，值小的，则添加进新的头节点，并且头节点和值小的链表都往后移动，这样一直比较下去，直到一个链表比较完为止。如果最后还有一个链表不为null，那么直接添加进新的头节点。

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(0);//申请新的头节点
        ListNode cur = newHead; //使用cur来间接使用新的头节点
        //循环的条件是两个链表都不为null
        while(list1 != null && list2 != null) {
            if(list1.val<list2.val) {
                cur.next =  list1;
                list1 = list1.next; //往后走
                cur = cur.next; //往后走
            }else {
                cur.next =  list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        //如果哪个链表不为null，则直接添加进新的头节点
        if(list1!=null) {
            cur.next = list1;
        }
        if(list2!=null) {
            cur.next =list2;
        }
        return newHead.next; //返回新头节点的后面部分，因为newHead.val为0
    }
}

2.3 获取链表倒数第K个节点

题目：链表中倒数第K个节点

思路： 这道题也是一道数学题，我们仍然使用快慢指针的思想，让fast先走k-1步，然后让slow和fast一起走。知道fast.next为null。

代码实现：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    	//判断K值的合法性以及head是否为null
        if(k <= 0 || head==null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(k-1 != 0) {
            fast = fast.next;
            //这个if语句处理了当k值大于链表长度的情况，复杂度变低
            if(fast == null) {
                return null;
            }
            k--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

2.4 获取链表的中间节点

题目：链表的中间节点

**思路：**快慢指针，让fast的速度是slow的两倍,走完之后，slow指向的节点就是中间节点。

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //两个循环条件不能交换位置，不然空指针异常
        while(fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

2.5 单链表的逆置

题目：反转链表

思路： 使用头插法将后面的节点一个一个插在前面。

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null) {
            return null;
        }
        if(head.next==null) {
            return head;
        }
        ListNode cur = head.next; 
        head.next = null; //修改为null
        
        while(cur!=null) {
            ListNode curNext = cur.next; //一定要保存cur.next，因为cur在改变
            cur.next = head;  //修改cur的指向，指向原本的头节点
            head = cur; //改变头节点，cur成为新的头节点
            cur = curNext; //改变cur
        }
        return head;

    }
}

总结

以上就是今天要讲的内容，本文仅仅简单介绍了链表的使用以及几个面试题，链表在Java数据结构中非常重要，学习时要多与数学结合起来，多画图，多思考！文章来源地址https://www.toymoban.com/news/detail-616742.html

到了这里，关于Java中的链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！