[数据结构与算法]链表汇总（未完待续）

题解

双指针（快慢指针）

141. 环形链表

力扣传送门

思路一：快慢指针
假如两个人绕曹操跑步，跑的快的人必定追得上慢的人。这就是快慢指针的思想，所以通过设置步长为2和1的两个指针，从链表都出发，不断往后移，如果存在环形链表，两指针必定会相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(slow != null && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow!=null && fast == slow){
                return true;
            }
        }
        return false;
    }
}

思路二：HashSet集合，具体见下一题

142. 环形链表 II

力扣传送门

思路一：借助Set集合的唯一性，往Set添加节点，若链表有循环，说明节点会重复遇到。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head != null) {
            if(set.contains(head)) {
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }
}

思路二：双指针，节省空间
由于快慢指针只是判断链表中有环，并不能得出相遇点就是交叉点。所以需要了解其中的一点规律才能做出：快慢指针相遇时，慢指针走到交叉节点的路径等于从首节点走到交叉节点的路径
具体证明见力扣
简单理解如下图：-4到2等于3到2的距离，-4才是相遇点

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

剑指 Offer 22. 链表中倒数第k个节点

力扣传送门

思路一：list集合（代码略）
用list集合存放所有节点，然后通过get(size-k)即可返回结果

代码略

思路二：快慢指针
让b指针先走k步，然后a指针和b指针同时开始往后走，待b走完时，a所到的位置就是倒数第k个节点，保持因为a和b的距离一直保持是k。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {   
        ListNode tmp = head;//b指针
        while(k-- > 0) {//先走k步
            tmp = tmp.next;
        }
        while(tmp != null) {//同时走
            tmp = tmp.next;
            head = head.next;
        }
        return head;//a指针
    }
}

思路三：二次遍历
第一次先求长度len，第二遍历到len-k的位置即可

代码略

面试题 02.07. 链表相交

力扣传送门

思路一：HashMap
对每个节点进行计数（不是节点值，是节点的引用），若存在计数为2的，说明该节点为交点。

代码略

思路二：交换遍历
难以确定交点的原因在于两路径到达交点的长度不一致，于是我们可以通过交换路径实现长度一致。例如a路径长度是4，b路径长度是5，a遍历完就跳去遍历b，b遍历完就去遍历a，那么两者的长度就能得到互补，也就是9。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while(a!=b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;//b也可
    }
}

链表骚操作

237. 删除链表中的节点

力扣传送门

思路：节点删除
a->b->c->d，删除b，就是把a指向b的引用指向c即可。但是我们并不知道a指向b的引用，只知道有个引用指向b。a指向b这种属于引用删除，还有一种删除就是替换，既然删不了b，那就用c替换b，即b.val = b.next.val。对于c后面的节点就没必要用替换了，而是只需要删除c就可以，因为我们知道b指向c的引用，所以可以删除，即b.next = b.next.next

class Solution {
    public void deleteNode(ListNode node) {    	
        if(node == null) return;
        if(node.next!=null) {
            node.val = node.next.val; //替换
            node.next = node.next.next; //删除
        }        
    }
}

1290. 二进制链表转整数

思路：二进制与十进制的转化
101 = ((((0 x 2)+1) x 2)+0) x 2)+1=5
其实就是1 x 2² + 0 x 2¹ + 1 x 2⁰ ，上式就是高中的秦九韶算法

class Solution {
    public int getDecimalValue(ListNode head) {
        int res = 0;
        while(head != null) {
            res = res * 2 + head.val;
            head = head.next;
        }
        return res;
    }
}

面试题 02.01. 移除重复节点

思路：HashSet
根据Set集合唯一性，如果遇到重复，就进行链表元素移除即可

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        HashSet<Integer> set = new HashSet();
        ListNode front = head;
        ListNode current = head;
        
        while(current != null) {
            if(set.contains(current.val)) { //存在就移除
                front.next = current.next;
            } else {
                set.add(current.val);
                front = current;     //记录上一个节点，用于删除
            }        
            current = current.next;  //遍历一个
        }
        return head;
    }
}

改进：元素有范围，可使用数组代替Set

思路二：暴力双层for循环

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        ListNode first = head;        
        while(first != null) {
            ListNode front = first; 
            ListNode current = first.next;               
            while(current != null) {
                if(current.val == first.val) {
                    front.next = current.next;
                } else {
                    front = current;
                }
                current = current.next;                    
            }
            first = first.next;
        }
        return head;
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖