【算法】链表相关我又来打卡了

川长思鸟来 2021-07-24 18:33 309阅读 0赞

### 文章目录 ###

*  数据结构
 *   *  1.链表在Java中的实现
     *  2.链表和数组的区别
     *  3.链表的操作
     *   *  1.链表的插入操作
         *  2.链表的删除操作
         *  3.遍历链表
 *  算法
 *  快慢指针
 *   *  1.环形链表
     *  2.环形链表II
     *  3.相交链表

# 数据结构 #

## 1.链表在Java中的实现 ##

public class Node{ 
        //存储当前元素的值
        public Integer value;
        //存储下一个节点的引用
        public Node next;
        public Node(Integer value){ 
            this.value = value;
        }
    }

## 2.链表和数组的区别 ##

数组:

*  可实现随机访问,能通过索引访问到具体的值
 *  数组的内存是有限的,不能自动扩容
 *  查询快(O(1)),添加,删除,插入慢(O(n))

链表:

*  不能实现随机访问,只能通过遍历链表的方式依次寻找
 *  链表可以自动扩容
 *  添加,删除和插入速度快(O(1)),查询慢(O(n))

## 3.链表的操作 ##

### 1.链表的插入操作 ###

![image-20201028110654944][]

public static void add(Node cur,Node prev){ 
        cur.next = prev.next;
        prev.next = cur;
    }

### 2.链表的删除操作 ###

![image-20201028111110278][]

/** *代码演示只写了主要的逻辑过程 *因此我们默认提供了cur节点和cur节点的前序节点prev **/
    public Node delete(Node cur,Node prev){ 
        prev.next = cur.next;
    }

注意:如果要删除的是该链表的头结点,我们只需要将头结点指向之前头结点的next就相当于删除了头结点

![image-20201028112011934][]

### 3.遍历链表 ###

*  链表没有固定的大小,因此我们遍历链表要判断链表是否到了最后一个节点
 *  在链表中,一般用链表的头结点来代表该链表

public void loop(Node node){
    	while(node !=null){
    		head = head.next;
    	}
    }

# 算法 #

# 快慢指针 #

链表中常用的算法思想:**快慢指针**

**快慢指针**

![image-20201028194707519][]

龟兔赛跑的问题，兔子和乌龟在同一个起点出发，乌龟每次移动一步，兔子每次移动两步，如果一个链表是有环的，那么兔子和乌龟是一定会相遇的（兔子超过乌龟一圈或者多圈）。

\*\*注意在代码中快慢指针的起始位置不同：\*\*因为我们链表不能使用for循环，而是使用while循环，条件是先于循环体判断的，如果设置两个指针在同一个起始点，那么直接就会跳出循环。

**因此我们将慢指针设置为head(头结点),快指针设置为head.next(头结点的下一个节点)**

当然也可以使用do while循环,将快慢指针都设置为头结点。

**注意使用快慢指针时，需要判断边界条件：**

1.  快指针的当前节点不能是null，如果为null说明了该链表不是环形的，快指针已经到达了链表的边界
2.  快指针的下一个节点不能是null，因为我们快指针每次都是移动两个结点，如果快指针的下一个节点是null，那么就无法指向快指针的下下个节点，造成了空指针异常。
3.  如果使用while循环，那么头结点和头结点的下一个节点都应该判断不为null，不然快指针的赋值语句空指针异常
4.  如果使用dowhile循环，那么只需要保证头结点不为null

## 1.环形链表 ##

![image-20201028201322557][]

**哈希表**

思路:判断一个链表有环,我们只需要将每个节点都存入一个不允许重复的数据结构,然后就可以判断链表是否是有环的

public class Solution { 
        public boolean hasCycle(ListNode head) { 
            Set<ListNode> seen = new HashSet<ListNode>();
            while (head != null) { 
                if (!seen.add(head)) { 
                    return true;
                }
                head = head.next;
            }
            return false;
        }
    }

时间复杂度是O(n):最坏的情况下我们需要变量每一个节点一次。

**快慢指针**

public class Solution { 
        public boolean hasCycle(ListNode head) { 
            if(head == null || head.next == null){ 
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while(slow != fast){ 
                //关于为什么要用快指针作为判断条件
                //因为快指针一定比慢指针更快的到达边界(不是环形链表的话)
                if(fast == null || fast.next == null){ 
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

## 2.环形链表II ##

![image-20201028210905076][]

思考:

比环形链表多出的步骤是要确定何时是整个链表环的入口

对于哈希表的处理方式来讲,当再次向哈希Set中添加同样的元素的时候就是这个链表的入口,直接将该节点返回即可。

而对于快慢指针的解法，这个思考策略较为复杂。

## 3.相交链表 ##

这是一道浪漫的题【错的人总会离开，对的人总会相遇】

![image-20201028221209344][]

**纯暴力**

使用双层for loop遍历链表headA,看headB是否有元素出现在headA中

这个算法不太推荐,因此不书写了,知道能这样处理就可以了

**哈希表**

遍历链表A将节点都存在哈希表中,然后再遍历链表B,发现了重复的节点就返回,就是相交的节点。

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            if(headA == null || headB == null){ 
                return null;
            }
            Set<ListNode> set = new HashSet<ListNode>();
            while(headA != null){ 
                set.add(headA);
                headA = headA.next;
            }
            while(headB != null){ 
                if(!set.add(headB)) { 
                    return headB;
                }
                headB = headB.next;
            }
            return null;
        }
    }

**双指针**

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
        //tempA和tempB我们可以认为是A,B两个指针
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) { 
            //如果指针tempA不为空，tempA就往后移一步。
            //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
            tempA = tempA == null ? headB : tempA.next;
            //指针tempB同上
            tempB = tempB == null ? headA : tempB.next;
        }
        //tempA要么是空，要么是两链表的交点
        return tempA;
    }

让指针tempA指向headB（注意这里是headB不是tempB）  
tempA = tempA == null ? headB : tempA.next;  
//指针tempB同上  
tempB = tempB == null ? headA : tempB.next;  
\}  
//tempA要么是空，要么是两链表的交点  
return tempA;  
\}

[image-20201028110654944]: /images/20210724/3220467dff9643948ba045324f042bae.png
[image-20201028111110278]: /images/20210724/2a78468940e8480481a83e50b509aec1.png
[image-20201028112011934]: /images/20210724/95de7635ef544eb28840409c9d648e47.png
[image-20201028194707519]: /images/20210724/6dee7cfc44494ae6aabf24790f2e2236.png
[image-20201028201322557]: /images/20210724/c19b5309a66d4734a47f25971ac4dcf8.png
[image-20201028210905076]: /images/20210724/30a0a66f7d54400d8cd65c6ff2675f34.png
[image-20201028221209344]: /images/20210724/5983c171c20449d197490e2e474593de.png