力扣 链表

每次生病之后都特别的虚弱，好累、、
本来以为周二可以更新的，结果公司的事情一件接着一件，就应接不暇了

23、合并K个升序链表

这段代码使用了优先级队列，且要求放进这个队列的数据都是按照从小到大的顺序
(a, b)->(a.val - b.val));
大的放在后面、、、

  // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val));

/**
 * 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 mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

86、分隔链表


链表、数组、栈、队列、树、图都是计算机专业的基本功了


/**
 * 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 partition(ListNode head, int x) {
        if(head==null || head.next==null) return head;

        ListNode node1=head,node1Pre=new ListNode(-1,head),newHead=node1Pre;
        while (node1!=null && node1.val<x){
            node1Pre=node1;
            node1=node1.next;
        }

        node1Pre.next=null;
        if(node1==null) return head;
        ListNode node2=node1;

        while (node2.next!=null){
            if(node2.next.val<x){
                ListNode temp=node2.next;
                node2.next=node2.next.next!=null?node2.next.next:null;
                node1Pre.next=temp;
                node1Pre=node1Pre.next;
            }else {
                node2=node2.next;
            }

        }

        node1Pre.next=node1;
        return newHead.next;
    }
}

83、删除排序列表中的重复元素


/**
 * 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 deleteDuplicates(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode cur=head;
        while (cur.next!=null){
            if(cur.val==cur.next.val){
                cur.next=cur.next.next;
            }else {
                cur=cur.next;
            }
            
        }
        return head;
    }
}

82、删除排序列表中的重复元素二


/**
 * 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 deleteDuplicates(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode head1=new ListNode(-1,head);
        ListNode pre=head1,cur=head;
        boolean flag=false;
        while (cur!=null && cur.next!=null){
            while (cur.next!=null && cur.val==cur.next.val){
                cur.next=cur.next.next;
                flag=true;
            }
            // if(cur.next==null) break;
            if(flag){
                cur=cur.next;
                pre.next=cur;
                flag=false;
            }else {
                pre=cur;
                cur=cur.next;
            }
        }
        
        return head1.next;
    }
}

80、删除有序数组中的重复项 II

思路


class Solution {
    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        if(length<=2) return length;

        int size=length;

        for (int i = 0; i < size; i++) {
            int j=i,count=0;
            while (j+1<size){
                if(nums[j]==nums[j+1]){
                    count++;
                    j++;
                }else {
                    break;
                }
            }

            if(count>=2){
                int left=i+2,right=i+count+1;
                while (right<size){
                    nums[left++]=nums[right++];
                }
                size=size-count+1;
                i++;
            }
            
            
        }
        return size;

    }
}

别人的题解：


class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 快慢指针，维护 nums[0..slow] 为结果子数组
        int slow = 0, fast = 0;
        // 记录一个元素重复的次数
        int count = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                // 此时，对于 nums[0..slow] 来说，nums[fast] 是一个新的元素，加进来
                slow++;
                nums[slow] = nums[fast];
            } else if (slow < fast && count < 2) {
                // 此时，对于 nums[0..slow] 来说，nums[fast] 重复次数小于 2，也加进来
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
            count++;
            if (fast < nums.length && nums[fast] != nums[fast - 1]) {
                // fast 遇到新的不同的元素时，重置 count
                count = 0;
            }
        }
        // 数组长度为索引 + 1
        return slow + 1;
    }
}

上题思路看不懂可以直接看下面的

26. 删除有序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                // 维护 nums[0..slow] 无重复
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // 数组长度为索引 + 1
        return slow + 1;
    }
}
// 详细解析参见：
// https://labuladong.gitee.io/article/?qno=

141、环形链表

这其实是一道数学题，为什么你走一步我走两步，有环的时候咱俩就能相遇、、

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针走到末尾时停止
        while (fast != null && fast.next != null) {
            // 慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明含有环
            if (slow == fast) {
                return true;
            }
        }
        // 不包含环
        return false;
    }
}
// 详细解析参见：
// https://labuladong.gitee.io/article/?qno=

142. 环形链表 II


原理也简单说下吧，我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步:



fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点：



所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

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

        }
        // 上面的代码类似 hasCycle 函数
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }

        // 重新指向头结点
        slow = head;

        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
// 详细解析参见：
// https://labuladong.gitee.io/article/?qno=

小学奥数不好好学，终究是老大徒伤悲啊~~~

160. 相交链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int alength = getLength(headA);
        int blength = getLength(headB);
        
        ListNode longNode = alength > blength ? headA : headB;
        ListNode shortNode = blength < alength ? headB : headA;

        ListNode start = getStart(longNode, Math.abs(alength - blength));
        while (start!=null && shortNode!=null){
            if(start==shortNode) return start;
            if(start.next==shortNode.next) return start.next;
            shortNode=shortNode.next;
            start=start.next;
        }
        return null;
    }
    public ListNode getStart(ListNode node,int count){
        while (count>0){
            count--;
            node=node.next;
        }
        return node;
    }
    
    public int getLength(ListNode node){
        int count=0;
        while (node!=null){
            count++;
            node=node.next;
        }
        return count;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容