# 148. Remove linked list elements

Difficulty: simple

Collection

Give you a head node of the linked list and an integer val. please delete all nodes in the linked list that meet the requirements Val = = Val node and returns a new header node.

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: []

Tips:

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. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: head=ListNode(next=head) pre=head while pre.next: if pre.next.val == val: pre.next=pre.next.next else: pre=pre.next return head.next

# 53. Rotating linked list

Difficulty: medium

Collection

Give you a head node of the linked list. Rotate the linked list and move each node of the linked list k positions to the right.

Example 1:

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

Example 2:

Input: head = [0,1,2], k = 4 Output:[2,0,1]

Tips:

- The number of nodes in the linked list is within the range [0, 500]
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if not head: return None length=0 temp=head while temp.next: length+=1 temp=temp.next temp.next=head k=k%(length+1) temp=head for i in range(length-k): temp=temp.next head=temp.next temp.next=None return head

# 20. Merge two ordered linked lists

Difficulty: simple

Collection

Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4] Output:[1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = [] Output:[]

Example 3:

Input: l1 = [], l2 = [0] Output:[0]

Tips:

- The number of nodes in the two linked lists ranges from [0, 50]
- -100 <= Node.val <= 100
- l1 and l2 are arranged in non decreasing order

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1: return list2 if not list2: return list1 ls = ListNode() tail = ls while list1 and list2: if list1.val < list2.val: ls.next = list1 ls = ls.next list1=list1.next else: ls.next = list2 ls = ls.next list2=list2.next if list1: ls.next=list1 if list2: ls.next=list2 return tail.next

# 131. Cross linked list

Difficulty: simple

Collection

Here are the head nodes headA and headB of the two single linked lists. Please find and return the starting node where the two single linked lists intersect. If there is no intersecting node between the two linked lists, null is returned.

As shown in the figure, two linked lists intersect at node c1 * *:**

The title data ensures that there are no links in the whole chain structure.

Note that after the function returns the result, the linked list must maintain its original structure.

Custom profiling:

The input of the evaluation system is as follows (the program you designed does not apply to this input):

- intersectVal - the value of the starting node of the intersection. If there are no intersecting nodes, this value is 0
- listA - the first linked list
- listB - second linked list
- Skippa - the number of nodes that jump to the cross node in listA (starting from the head node)
- skipB - the number of nodes that jump to the cross node in listB (starting from the head node)

The evaluation system will create a linked data structure based on these inputs and pass the two head nodes headA and headB to your program. If the program can correctly return the intersection node, your solution will be regarded as the correct answer.

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 value of intersection node is 8 (note that if two linked lists intersect, it cannot be 0). The linked list starts from the respective header A by [4,1,8,4,5]，Linked list B by [5,6,1,8,4,5]. stay A In, there are 2 nodes before the intersecting node; stay B In, there are 3 nodes before the intersection node.

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 value of intersection node is 2 (note that if two linked lists intersect, it cannot be 0). The linked list starts from the respective header A by [1,9,1,2,4]，Linked list B by [3,2,4]. stay A In, there are 3 nodes before the intersection node; stay B In, there is 1 node before the intersection node.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: null Explanation: the linked list starts from the respective header A by [2,6,4]，Linked list B by [1,5]. Because the two linked lists do not intersect, so intersectVal Must be 0, and skipA and skipB Can be any value. The two linked lists do not intersect, so they return null .

Tips:

- The number of nodes in listA is m
- The number of nodes in listB is n
- 1 <= m, n <= 3 * 104
- 1 <= Node.val <= 105
- 0 <= skipA <= m
- 0 <= skipB <= n
- If listA and listB have no intersection, intersectVal is 0
- If listA and listB have an intersection, intersectVal == listA[skipA] == listB[skipB]

**Advanced: * * can you design a solution with time complexity O(m + n) and only O(1) memory?

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: p=headA q=headB while p!=q: if p: p=p.next else: p=headB if q: q=q.next else: q=headA return p

# 70. Delete the duplicate Element II in the sorting linked list

Difficulty: medium

Collection

Given the head of a sorted linked list, delete all nodes with duplicate numbers in the original linked list, leaving only different numbers. Returns the sorted linked list.

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]

Tips:

- The number of nodes in the linked list is within the range [0, 300]
- -100 <= Node.val <= 100
- The title data ensures that the linked list has been arranged in ascending order

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: dummy=ListNode() dummy.next=head p=dummy while p.next: q=p.next while q and q.val==p.next.val: q=q.next if p.next.next==q: p=p.next else: p.next=q return dummy.next