【算法】回文链表，相交链表，链表元素的删除，反转链表和思考策略（双指针，哨兵节点）

深藏阁楼爱情的钟 2021-07-25 00:15 285阅读 0赞

# 数据结构 #

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

## 4.反转链表 ##

![image-20201031210434275][]

分析:

让快指针的节点的指针指向慢节点,然后快慢节点都往链表后移(需要先将快节点的下一个指针保存下来)

class Solution { 
        public ListNode reverseList(ListNode head) { 
            //可以加个特殊判断
            if(head == null || head.next == null){ 
                return head;
            }
            ListNode pre = head;
            ListNode cur = head.next;
            while(head != null) { 
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
        }
    }

## 5.移除链表中的元素 ##

![image-20201031203833135][]

分析:删除的是链表中节点值等于val的所有的节点,返回的是删除之后的链表

思路:

*  删除链表中的所有val的节点--------遍历链表的所有元素
 *  如何删除--------判断节点的val值,相等就删除,不相等就指针后移一位
 *  特别注意:很可能会删除的节点是第一个,那么这是我们为了保证链表一定是有头的,这里使用了哨兵节点的技术

class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
            ListNode myhead = new ListNode(0);
            myhead.next = head;
            
            ListNode pre = myhead;
            ListNode cur = head;
            while(cur != null){ 
                if(cur.val == val){ 
                    pre.next = cur.next;
                }else{ 
                    pre = cur;
                }
                cur = cur.next;
            }
            //返回myhead的下一个节点,因为之前的head节点的值可能会被删除了,这时如果返回head,那么就会返回[]
            return myhead.next;
        }
    }

**要注意在链表中删除,插入添加等操作时为了保证链表一定是有头的或者一定是有尾的可以使用哨兵节点的技术**,哨兵节点并没有任何实际的意义,仅仅是功能意义,为了操作方便而已。

就类似于有的题目会自带一个头结点，而头结点是不含任何的信息的。

## 6.回文链表 ##

![image-20201031210524787][]

转化为判断数组是否是回文数组

*  将链表中的值都存入数组中(要创建的是动态数组)
 *  双指针数组判断回文数组(头尾指针)

> 数组是可以通过索引取值的,利用的是内存寻址系统

class Solution { 
        public boolean isPalindrome(ListNode head) { 
            List<Integer> list = new ArrayList<Integer>();
            while(head != null){ 
                list.add(head.val);
                head = head.next;
            }
            int fomer = 0;
            int back = list.size() - 1;
            while(fomer < back){ 
                if(!list.get(fomer).equals(list.get(back))){ 
                    return false;
                }
                fomer++;
                back--;
            }
            return true;
        }
    }

## 7.删除链表中的节点 ##

![image-20201031211215933][]

分析:给一个节点,然后让删除该节点,并且该节点不是末尾的节点,那么该节点一定是有尾节点的.

思路:直接将该节点的信息改为了它的下一个节点的信息。

class Solution { 
        public void deleteNode(ListNode node) { 
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }

## 8.删除链表的节点II ##

![image-20201031211657948][]

分析：

条件：

*  给了链表和头结点，和一个int值，该int值是节点中存储的数据
    
     *  删除的节点的位置不固定，可能是链表中的任意位置（可能是头，也可能是尾）

思路1：**搬移数据改变指针指向**

*  遍历链表找到节点的位置
 *  改变要删除的值的为下一个节点的值，其指向对应改变

class Solution { 
        public ListNode deleteNode(ListNode head, int val) { 
            // ListNode myhead = new ListNode(0);
    // myhead.next = head;
    // while (head != null){ 
    // if (head.val == val){ 
    // head.val = head.next.val;
    // head.next = head.next.next;
    // }else{ 
    // head = head.next;
    // }
    // }
    // return myhead.next;
        }
    }

*  该解法思路是对的,但是细节会发生错误,假如要删除的节点是最后一个节点就会发生错误,空指针

思路2:**使用双指针改变指针指向**

class Solution { 
        public ListNode deleteNode(ListNode head, int val) { 
            if(head == null){ 
                return head;
            }
            //使用哨兵节点,保证链表一定是有头的
            //这样假如删除的是第一个节点,我们也能正常返回
            ListNode myhead = new ListNode(0);
            myhead.next = head;
            
            ListNode pre = myhead;
            ListNode cur = head;
            while(cur != null){ 
                if(cur.val == val){ 
                    pre.next = cur.next;
                }else{ 
                    pre = cur;
                }
                cur = cur.next;
            }
            return myhead.next;
        }
    }

总结:

*  删除时要判断是否删除节点的位置
    
     *  有可能删除头就用哨兵
     *  有可能删除尾就用双指针
     *  如果不可能删除尾可以直接搬移数据,改变指针指向

ListNode pre = myhead;
            ListNode cur = head;
            while(cur != null){ 
                if(cur.val == val){ 
                    pre.next = cur.next;
                }else{ 
                    pre = cur;
                }
                cur = cur.next;
            }
            return myhead.next;
        }
    }

总结:

*  删除时要判断是否删除节点的位置
    
     *  有可能删除头就用哨兵
     *  有可能删除尾就用双指针
     *  如果不可能删除尾可以直接搬移数据,改变指针指向
 *  是删除一个节点还是所以的节点

[image-20201028110654944]: /images/20210724/e83b74a7cac74504b5a012b5807f2dec.png
[image-20201028111110278]: /images/20210724/5c37aa543e4545b89bbec8cc23a6f910.png
[image-20201028112011934]: /images/20210724/a7d8ed0aa4f04eca81a489b8153c9732.png
[image-20201028194707519]: /images/20210724/480f5499e3b94ab4834a539ddf7dc2d5.png
[image-20201028201322557]: /images/20210724/9211a606bf7945e8ba827c4b3a422e5e.png
[image-20201028210905076]: /images/20210724/3620af6e21144c0888a67ffb92000d00.png
[image-20201028221209344]: /images/20210724/6a20c3375e5f405891f62e8054a04206.png
[image-20201031210434275]: /images/20210724/b55c8c5183ac4ff4bd27fcb5e735fa47.png
[image-20201031203833135]: /images/20210724/cececc1e3aae472f92a4ae75df881696.png
[image-20201031210524787]: /images/20210724/6af16bd2e89c40adb0a18f522be65534.png
[image-20201031211215933]: /images/20210724/1c20ac2622e74c9cab00d3a55c0bc890.png
[image-20201031211657948]: /images/20210724/e9789b6fc14c43b98168057d8cf6b27d.png