[数据结构与算法]leetcode 链表总结-java

题目所属分类

关于链表的题目

链表题目的心得

1 哨兵

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head结点都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫做带头链表。
这种做法多了一个节点的开销，但对于一些会操作到head结点的题目，会方便很多。例如上面的删除倒数第N个元素，倒置链表Ⅱ等。

2 分链解题

例如 No.86 Partition List（分隔链表），No.328 Odd Even Linked List（奇偶链表），可以考虑设置两个链表，将原有链表分为两个各自满足一定条件的链表，最终再将链表进行结合。

3 测试用例

在解答过程中，我一般考虑一下的边界条件：

链表为空
链表中只有一个结点
链表中只包含两个结点
代码在处理头结点跟尾结点是否存在什么问题

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

代码案例：输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head ;
        ListNode p = dummy ;
        while(p != null &&  p.next !=null){
            if(p.next.val == val ){
                p.next  =  p.next.next;
            }else {
                p = p.next ;
            }
        }
        return dummy.next;
    }
}

206. 反转链表（模板记住）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

迭代解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null ;
        ListNode a = head , b = head.next ;
        while(b != null){
            ListNode c = b.next ;
            b.next = a ;//让第二个的指针 指向前一个
            a = b ;//a和b依次往后移动一位
            b = c;//所以这个时候要保存b,next点
        }
        head.next = null ;//反转之后的头结点变成了尾结点 所以head.next = null 
        return a ;//最后返回反转后的头节点a
    }
}

递归解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {//递归的话  把它当作黑箱子操作
    //考虑边界情况 为空或者 只有一个情况下 只需要返回头节点就可以了
        if(head == null || head.next == null) return head ;
        ListNode tail = reverseList(head.next);//以head.next为头的翻转 返回的是翻转后的头节点
        head.next.next = head ;//翻转后的尾节点 指向头节点
        head.next = null;            //头节点变成尾结点
        return tail ;//返回翻转后的头节点
    }
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

题解

分成三部分 一个是将后半段进行翻转
二是前后要对称
三是后一半要翻转回去 不翻转回去可能会出现死循环的问题 但是试了试 不翻转回去也可以 没报错

翻转之后

数数的方法 没有用快慢指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        //知道链表的长度
        int n =  0;
        for(ListNode p = head ; p != null ; p = p.next ) n++;
        if(n <= 1 ) return true ;
        int half = n / 2;
        ListNode a = head ; 
        //找到要翻转的起点
        for(int i = 0 ; i < n - half   ;i++){// 要跳n-half次
        a = a.next;
        }
        ListNode b = a.next;
        //开始翻转
        for(int i = 0 ; i < half - 1 ; i++){
            ListNode c = b.next ;
            b.next = a;
            a = b ;
             b = c ;
        }
        //然后用两个指针 检查是否对称
        ListNode p = head , q = a ;
        boolean success = true ;
        for(int i = 0 ; i < half ; i++){
            if(p.val != q.val){
                success = false;
               break;
            }
            p = p.next ;
            q = q.next ;
        } 
        //将后一半翻转回去
        ListNode tail = a;
        b = a.next ;
         for(int i = 0 ; i < half - 1 ; i++){
            ListNode c = b.next ;
            b.next = a;
            a = b ;
             b = c ;
        }
        tail.next = null ;
        return success;
    }
}

快慢指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
       if(head == null || head.next == null) return true;
        ListNode slow = head, fast = head.next;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //快慢指针 这时候慢指针到达一半
        //将右半部分的链表slow.next进行反转
        ListNode right = reverse(slow.next);
        //双指针
        ListNode p = head ;
        while(right != null ){
            if(p.val != right.val) return false;
            p = p.next ;
            right = right.next;
        }
        return true ;
           
         
    }
    public ListNode reverse(ListNode head){//翻转链表模板
        ListNode a = head , b = head.next;
        while(b != null){
             ListNode c = b.next ;
             b.next = a;
             a = b ; b = c ;
        }
       
        head.next = null ;
        return a ;
    }
}

237. 删除链表中的节点

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

题解

(链表操作) O(1)O(1)
由于是单链表，我们不能找到前驱节点，所以我们不能按常规方法将该节点删除。
我们可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。

时间复杂度分析：只有常数次操作，所以时间复杂度是 O(1) 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

21 合并链表

环型链表所考的类型题 环入口 判断环 环个数 环种有几个节点
剑指offer 34. 链表中环的入口结点-java实现

环型链表(判断环)

题解

有环一定会相遇 无环的话快指针会走到空结点
用两个指针从头开始扫描，第一个指针每次走一步，第二个指针每次走两步。如果走到 null，说明不存在环；否则如果两个指针相遇，则说明存在环。

为什么呢？
假设链表存在环，则当第一个指针走到环入口时，第二个指针已经走到环上的某个位置，距离环入口还差 xx 步。
由于第二个指针每次比第一个指针多走一步，所以第一个指针再走 xx步，两个指针就相遇了。

时间复杂度分析：第一个指针在环上走不到一圈，所以第一个指针走的总步数小于链表总长度。而第二个指针走的路程是第一个指针的两倍，所以总时间复杂度是 O(n) 。

/**
 * 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 || head.next == null)return false;
        ListNode one = head ;
        ListNode second = head ;
        while(second.next != null && second.next.next != null){
                one = one.next;
                second = second.next.next;
                if(one == second) return true;
        }
        return false;
    }
}

判断环形的入口节点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null ;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                slow = head;
                while(slow != fast){
                     slow = slow.next;
                    fast = fast.next ;
                }
               return slow ;
            }
        }
        return null ;
    }
}

143. 重排链表

148. 排序链表

92. 反转链表 II

61. 旋转链表

LeetCode 82. 删除排序链表中的重复元素 II

LeetCode 83. 删除排序链表中的重复元素

86. 分隔链表

328. 奇偶链表

leetcode 19. 删除链表的倒数第 N 个结点-java实现

leetcode 21. 合并两个有序链表-java版

leetcode 23. 合并K个升序链表-java版