【数据结构】-- LinkedList与链表（1）-EW帮帮网

文章目录

1. ArrayList的缺陷
2. 链表
- 2.1 链表的概念及结构
- 2.2 链表的实现
3. 链表面试题

1. ArrayList的缺陷

ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
链式结构在逻辑上是连续的，但是在物理上不一定连续。

链表是一个一个的称为节点的对象组成的。这个节点至少有两个域，一个是value域（用来存放数据的），还有一个叫做next域（存放节点对象的地址）。
在这里插入图片描述

链表共有八种数据结构：

单向或者双向

带头或不带头

循环或非循环

重点掌握的两种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

无头双向链表： 在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 链表的实现

public class MySingleList {
    static class ListNode{
        public  int value;
        public ListNode next;
        //构造方法
        public ListNode(int value){
            this.value = value;
        }
    }
    public ListNode head;

    /**
     * 链表的创建
     */
    public void createList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
    }

    /**
     * 链表的遍历
     *
     * 问：为什么不直接让head走，而是定义一个中间变量cur呢？
     * 答：如果直接使用head来遍历链表的话，我们的head在遍历一次之后就走到了链表的尾端，
     *     就不能再次进行遍历了，就相当于head的这个信息就不存在了
     */
    public void show(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 求链表的长度
     * @return
     */
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 是否包含数据key
     * @param key  要查找的元素
     * @return  返回是否找到
     */
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null){
            if (cur.value == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

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

    /**
     * 尾插法
     * @param data
     */
    public void addLast(int data){
        ListNode node = new ListNode(data);
        //head为空
        if (head == null){
            head = node;
            return;
        }
        //1. 找尾巴
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }


    /**
     * 在任意位置插入一个节点
     *
     * 1. index = 0，头插法
     * 2. index = len，尾插法
     * 3. 找到index的位置的前一个节点
     * 4. 开始进行插入
     * @param index
     * @param data
     */
    public void insertNode(int index, int data){
        if (index < 0 || index > size()){
            return;
        }
        if (index == 0){
            addFirst(data);
        }else if (index == size()){
            addLast(data);
        }else {
            ListNode node = new ListNode(data);
            ListNode cur = finIndex(index);
            node.next = cur.next;
            cur.next = node;
        }
    }

    /**
     * 找到index位置的前一个节点
     * @param index
     * @return
     */
    private ListNode finIndex(int index){
        ListNode cur = head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 删除第一个出现关键字key的节点
     *
     * 1. cur要走到删除节点的前一个节点的位置
     * @param key
     */
    public void remove(int key){
        //链表为空
        if (head == null){
            return;
        }
        //要删除的节点为头节点
        if (head.value == key){
            head = head.next;
            return;
        }
        ListNode cur = findKey(key);
        //没有要删除的数据
        if (cur == null){
            return;
        }
        //删除节点
        cur.next = cur.next.next;
    }

    /**
     * 找到要删除的key的前一个节点
     * @param key 
     * @return
     */
    public ListNode findKey(int key){
        ListNode cur = head;
        while (cur.next != null){
            if (cur.next.value == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;//没有找到返回nul
    }

    /**
     * 删除所有的关键字key的节点
     * @param key
     */
    public void removeAllKey(int key){
        //链表为空
        if (head == null){
            return;
        }

        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null){
            if (cur.value == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.value == key){
            head = head.next;
        }
    }


    /**
     * 要实现每一个节点的内存得到回收
     * 1. head = null
     * 2. 将每个节点的next域和value域都置为空
     */
    public void clear(){
        ListNode cur = head;
        while (cur != null){
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN.next;
        }
        head = null;
    }
}

3. 链表面试题

3.1 移除链表元素

在线oj
在这里插入图片描述

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        if(head == null) return null;
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == val){
                cur = cur.next;
                prev.next = cur;
            }else{
                prev = cur;
                cur = cur.next;    
            }
        }
        return head;
    }
}

3.2 反转链表

在线oj
在这里插入图片描述

这里的链表反转是指链表的结构反转。

/**
    利用链表的头插法
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }
}

3.3 链表的中间结点

在线oj
在这里插入图片描述

解法一（遍历链表两遍）：

求链表的长度len

走len/2步

解法二：快慢双指针算法（只遍历链表一遍）
fast走两步，slow走一步。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

3.4 返回链表的倒数第k个节点

在线oj
在这里插入图片描述

解题思路：

fast = head，slow = head

fast走k-1步

fast 和 slow一起往前走，fast走到链表的尾时，slow所指向的位置就是倒数第k个节点的位置。

class Solution {
    public int kthToLast(ListNode head, int k) {
        if (k <= 0){
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k-1; i++) {
            if (fast == null){
                return -1;
            }
            fast = fast.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

3.5 合并两个有序链表

在线oj
在这里插入图片描述

解题思路：

定义一个傀儡结点newH

定义headA、headB两个结点分别指向两个链表的头。

比较headA.value 和 headB.value的大小

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();
        ListNode tempH = newHead;
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                tempH.next = list1;
                tempH = tempH.next;
                list1 = list1.next;
            }else {
                tempH.next = list2;
                tempH = tempH.next;
                list2 = list2.next;
            }
        }
        //拼接上去没有走完的链表
        if (list1 != null){
            tempH.next = list1;
        }
        if (list2 != null){
            tempH.next = list2;
        }
       return newHead.next;
    }
}

3.6 链表分割

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

在这里插入图片描述

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode cur = pHead;
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        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;
        }
        if (as != null){
            ae.next = null;
        }
        be.next = as;
        return bs;
    }
}

3.7 链表的回文结构

在线oj
在这里插入图片描述

解题思路:

找到中间结点

反转中间结点以后的链表

head —> <—slow

public class PalindromeList {
    
    public boolean chkPalindrome(ListNode head) {
        if (head == null){
            return false;
        }
        //1. 找到中间结点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        //2. 反转中间节点之后的数据
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        //3. 判断是否是回文结构
        while (head != slow ){
            if (head.val != slow.val){
                return false;
            }
            if (head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

3.8 相交链表

在线oj
在这里插入图片描述

解题思路：

求2个链表的长度lenA lenB

根据链表的长度确定哪个链表长，长的链表用pl指向，短的链表用ps指向

让长的链表先走差值步，len =Math.abs(lenA-lenB)pl走

一起走，下次相遇之后就是交点

public class Solution {
    public int length(ListNode head){
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        //1. 求两个链表的长度，假设A链表最长
        int lenA = length(headA);
        int lenB = length(headB);

        //2. 根据链表的长度 确定pl ps 的指向
        if (lenA > lenB){
            ListNode pl = headA;
            ListNode ps = headB;
            //3. 让pl先走length= pl-ps步
            for (int i = 0; i < Math.abs(lenA-lenB); i++) {
                pl = pl.next;
            }
            //4. pl ps 一起往前走，直到相遇
            while (pl != null && ps != null){
                if (pl == ps){
                    return ps;
                }
                ps = ps.next;
                pl = pl.next;
            }
            return null;
        }else {
            ListNode pl = headB;
            ListNode ps = headA;
            //3. 让pl先走length= pl-ps步
            for (int i = 0; i < Math.abs(lenA-lenB); i++) {
                pl = pl.next;
            }
            //4. pl ps 一起往前走，直到相遇
            while (pl != null && ps != null){
                if (pl == ps){
                    return ps;
                }
                ps = ps.next;
                pl = pl.next;
            }
            return null;
        }
    }
}

3.9 环形链表

在线oj
在这里插入图片描述
【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，…n步行吗？

在这里插入图片描述

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

3.10 环形链表II

在线oj
在这里插入图片描述
结论：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇
证明：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        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;
    }
}

【数据结构】-- LinkedList与链表（1）

文章目录

1. ArrayList的缺陷

2. 链表

2.1 链表的概念及结构

2.2 链表的实现

3. 链表面试题

3.1 移除链表元素

3.2 反转链表

3.3 链表的中间结点

3.4 返回链表的倒数第k个节点

3.5 合并两个有序链表

3.6 链表分割

3.7 链表的回文结构

3.8 相交链表

3.9 环形链表

3.10 环形链表II

网站公告

今日签到

热门文章

最新发布