链表remove系列

本文主要是介绍链表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:

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:

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

Example 2:

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:

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

Example 2:

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:

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 7058488Add to ListShare

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

 

Example 1:

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

Example 2:

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:

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:

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:

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:

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 6596889Add to ListShare

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:

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:

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

Example 3:

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系列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！