链表双指针法

Scroll Down

链表中的经典问题就是链表中是否存在环,存在环,并且求出环的入口节点在哪,链表的中间节点是哪一个.

链表中是否存在环

这道题也有两个解法,用set存储判断法,快慢指针法

set存储判断

还是先来简单版本的,遍历链表,将出现过的节点都放到set中,如果后面有出现过,那就证明这个是有环的,如果循环到最后也没有出现,则认为是没有环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        Set<ListNode> set = new HashSet<>();
        int index = 0;
        while(head != null){   
	    //判断是否有环,有的话就直接return true,否则继续	
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
           //到最后就认为是没有环
        return false;
    }
}

双指针法解决链表是否有环问题

其实双指针联想到现实场景中,用跑步来是模拟是最好的了

有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。
但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

快慢指针法就是用了这种思想进行判断

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //使用快指针进行判断
        while(fast != null){
	    //这里必须要判断一下,否则就有可能快指针会空指针异常,如果确认有终点,则认为这是没有环	
            if(fast.next == null){
                return false;
            }
	//快指针走两步
            fast = fast.next.next;
	//慢指针走一步
            slow = slow.next;
	//如果相遇的话,则证明有环,否则快指针一定会走到终点
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

双指针法判断环的入口是哪一个节点

判断链表中是否有环,并且环的入口是哪一个

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。

**说明:**不允许修改给定的链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

环形链表题目1

示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

环形链表题目1

示例 3:

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

环形链表题目3

在快慢指针相遇时,这时重新声明一个指针,指向指针头,然后由快指针和第三个指针进行同步走,当两者相遇时,一定是在环的入口

链表中环的入口

​ 由此得出F = B,所以,当快指针从相遇点开始走的时候,第三个指针从head开始走,当他们相遇时即环的入口

public class Solution {
   public ListNode detectCycle(ListNode head) {
       //快指针
       ListNode fast = head;
       //慢指针
       ListNode slow = head;
       while(fast != null){
         //如果快指针到达终点,证明没有环,返回null
           if(fast.next == null){
               return null;
           }
           fast = fast.next.next;
           slow = slow.next;
           //如果有环的话,第三个指针从头开始走,快指针继续走
           if(fast == slow){
               ListNode third = head;
             //当快指针与第三个指针相遇时,证明到了环的入口
               while(fast != third){
                   third = third.next;
                   fast = fast.next;
               }
                return third;
           }
       }
       return null;
   }
}

双指针法删除倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。

​ 这道题核心的点就是如何判断倒数第N个节点在哪里,指针可以停放在那里,因为链表我们是不知道长度的,除非先遍历一遍,知道了长度,就知道倒数第N个节点是哪一个.如果在一次遍历的情况下,这种距离为N场景下,使用双指针法,首先快指针先走N+1步,然后慢指针再与快指针同步走,快指针走到终点时,慢指针这个时候就到了倒数第N+1个节点处,然后slow.next = slow.next.next;即可删除倒数第N个指针节点.

​ 删除倒数第N个节点的情况下,有删除头节点这种特殊情况,如果正常处理比较麻烦,需要判断是不是删除的头结点,但是我们在原有头结点之前,增加一个特殊的哨兵节点,不参与计算和删除,这样即使删除的是头结点,也可以直接按照正常的情况下,返回哨兵节点的next.哨兵节点的作用如图:

删除链表倒数第N个节点

代码实现如下:

package com.zhengyao.List.doublepointer;

import com.zhengyao.List.ListNode;

/**
 * @author : zhengyao3@郑瑶
 * @date : 2019/10/8 16:48
 * @Description: 删除链表的倒数第N个节点
 * 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
 *
 * 示例:
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后,链表变为 1->2->3->5.
 * 说明:
 *
 * 给定的 n 保证是有效的。
 *
 * 来源:力扣(LeetCode)
 * 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 */
public class Solution19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //哨兵节点
        ListNode tempHead = new ListNode(0);
        tempHead.next = head;
        //快指针
        ListNode fast = tempHead;
        //慢指针
        ListNode slow = tempHead;
        int index = 0;
        while(fast != null){
            //使用双指针法,快指针先走,快指针先走N+1步,这样两者相差步数为n,即找到了需要删除的那个节点,找到之后删除即可
            if(index >= n+1 ){
                slow = slow.next;
            }
            index++;
            fast = fast.next;
        }
        //删除节点
        slow.next = slow.next.next;
        //返回有效节点
        return tempHead.next;
    }
}