心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

链表remove系列

发布时间：2022-06-29 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了链表remove系列，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
203. Remove Linked List Elements
Easy

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

链表remove系列

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 104].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50
/**
 * 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 PRe = new ListNode(0);
        pre.next = head;
        ListNode curr = pre;
        while(curr.next!=null){
            if(curr.next.val==val) curr.next = curr.next.next;
            else curr=curr.next;
        }
        return pre.next;
    }
}
83. Remove Duplicates From Sorted List
Easy

Given the head of a sorted linked list, delete all duplicates such that each element apPEars only once. Return the linked list sorted as well.

Example 1:

链表remove系列

Input: head = [1,1,2]
Output: [1,2]

Example 2:

链表remove系列

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.
/**
 * 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) return null;
        ListNode curr= head;
        while(curr.next!=null){
            if(curr.val==curr.next.val) curr.next=curr.next.next;
            else curr=curr.next;
        }
        return head;
    }
}
82. Remove Duplicates from Sorted List II
Medium

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

链表remove系列

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

链表remove系列

Input: head = [1,1,1,2,3]
Output: [2,3] 

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

解法：首先这个题无法再用1个指针解决问题，需要有pre和curr两个指针，并且curr遇到有相同的节点时，要完全跳过这些节点

/**
 * 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) {
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode pre = dummy;
        ListNode curr = head;
        int count=0;
        while(curr!=null && curr.next!=null){
            if( curr.val==curr.next.val){//如果有重复，将重复节点全部跳过
                int temp=curr.val;
                while(curr!=null && curr.val==temp)  curr=curr.next;
                pre.next=curr;//将pre指向重复过后的节点
            }
            else{//如果没有重复，两个指针平行向右移动
                pre=pre.next;
                curr=curr.next;
            }
        }
        return dummy.next;
    }
}
19. Remove Nth Node From End of List
Medium

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

链表remove系列

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

解法：

这个题先把快指针移动都第n个位置，然后快慢指针同时向右移动，直至快指针到达结尾

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode slow= pre;
        ListNode fast=pre;
        for(int i=0;i<n;i++){
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return pre.next;
    }
}
1171. Remove Zero Sum Consecutive Nodes from Linked List
Medium

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list.  You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

  • The given linked list will contain between 1 and 1000 nodes.
  • Each node in the linked list has -1000 <= node.val <= 1000.

解法： 这个题用到了prefixsum的思想，

/**
 * 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 removeZeroSumSublists(ListNode head) {
        Map<Integer,ListNode> map = new HashMap();
        int sum=0;
        ListNode pre =new ListNode(0);
        pre.next=head;
        ListNode curr = pre;
        while(curr!=null){
            sum+=curr.val;
            map.put(sum,curr);
            curr=curr.next;
        }
        curr = pre;
        sum=0;
        while(curr!=null){
            sum+=curr.val;
            if(map.get(sum)!=null) curr.next=map.get(sum).next;//注意，这里如果找到相同的，那么要指向该相同节点的下一个节点
            curr=curr.next;
        }
        return pre.next;
    }
}
234. Palindrome Linked List
Easy

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

链表remove系列

Input: head = [1,2,2,1]
Output: true

Example 2:

链表remove系列

Input: head = [1,2]
Output: false

Constraints:

  • The number of nodes in the list is in the range [1, 105].
  • 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
/*
解法1:直接把list复制到array，然后左右两个指针checkparlindrome
解法2:快慢指针找到中点，反转后半部分后进行一一比对
*/
class Solution {
    public boolean isPalindrome(ListNode head) {
        //1.find the mid
        ListNode slow = head,fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast=fast.next.next;
        }
        //2.reverse second part
        ListNode tail = reverse(slow.next);
        //3.check
        ListNode First=head,last=tail;
        while(first!=null && last!=null){
            if(first.val!=last.val) return false;
            first=first.next;
            last=last.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr=head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
}

 

class Solution {
    public boolean isPalindrome(ListNode head) {
        //1.find the mid
        ListNode slow = head,fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast=fast.next.next;
        }
        //2.reverse second part
        ListNode tail = reverse(slow.next);
        //3.check
        ListNode first=head,last=tail;
        boolean flag = true;
        while(first!=null && last!=null){
            if(first.val!=last.val) {
                flag=false;//假如需要将list恢复原状
                break;
            }
            first=first.next;
            last=last.next;
        }
        slow.next = reverse(tail);//假如需要将list恢复原状
        return flag;
    }
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr=head;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
}
160. Intersection of Two Linked Lists
Easy

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

链表remove系列

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

  • intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
  • listA - The first linked list.
  • listB - The second linked list.
  • skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
  • skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

 

Example 1:

链表remove系列

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

链表remove系列

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

链表remove系列

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

 

Constraints:

  • The number of nodes of listA is in the m.
  • The number of nodes of listB is in the n.
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • intersectVal is 0 if listA and listB do not intersect.
  • intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.
Follow up: Could you write a solution that runs in O(n) time and use only O(1) ;memory?
/**
 * 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) {
        ListNode currA = headA,currB=headB;
        while(currA!=null || currB!=null){
            if(currA==null) currA=headB;
            if(currB==null) currB=headA;
            if(currA==currB) return currA;
            currA=currA.next;
            currB=currB.next;
        }
        return null;
    }
}
138. Copy List with Random Pointer
Medium

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

 

Example 1:

链表remove系列

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

链表remove系列

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

链表remove系列

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

 

Constraints:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random is null or is pointing to some node in the linked list.
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandoMList(Node head) {
        Map<Node,Node> map = new HashMap();
        Node pre = new Node(0);
        Node curr = pre;
        while(head!=null){
            curr.next = new Node(head.val);
            curr=curr.next;
            curr.random=head.random;
            map.put(head,curr);
            head=head.next;
        }
        curr = pre.next;
        while(curr!=null){
            curr.random=map.get(curr.random);
            curr=curr.next;
        }
        return pre.next;
    }
}

 

脚本宝典总结

以上是脚本宝典为你收集整理的链表remove系列全部内容，希望文章能够帮你解决链表remove系列所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：HashMapjavalinkedlistlistloadloadphppythonsortwhilewhile程序员程序员
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程