# 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:
while pre.next:
if pre.next.val == val:
pre.next=pre.next.next
else:
pre=pre.next
```

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]:
return None
length=0
while temp.next:
length+=1
temp=temp.next
k=k%(length+1)
for i in range(length-k):
temp=temp.next
temp.next=None
```

# 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
```

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).
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).
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
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:
while p!=q:
if p:
p=p.next
else:
if q:
q=q.next
else:
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()
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
```

Keywords: data structure leetcode linked list

Added by vronsky on Wed, 23 Feb 2022 12:48:47 +0200