Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb76b800

Browse files
add md articles (#5076)
* add delete-n-nodes-after-m-nodes-of-a-linked-list.md article* add insert-into-a-sorted-circular-linked-list.md article* add plus-one-linked-list.md article* add print-immutable-linked-list-in-reverse.md article
1 parent7f526f3 commitb76b800

File tree

4 files changed

+861
-0
lines changed

4 files changed

+861
-0
lines changed
Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
##1. Traverse Linked List and Delete In Place
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defdeleteNodes(self,head: Optional[ListNode],m:int,n:int) -> Optional[ListNode]:
8+
current_node= head
9+
last_m_node= head
10+
11+
while current_nodeisnotNone:
12+
# initialize m_count to m and n_count to n
13+
m_count, n_count= m, n
14+
15+
# traverse m nodes
16+
while current_nodeisnotNoneand m_count!=0:
17+
last_m_node= current_node
18+
current_node= current_node.next
19+
m_count-=1
20+
21+
# traverse n nodes
22+
while current_nodeisnotNoneand n_count!=0:
23+
current_node= current_node.next
24+
n_count-=1
25+
26+
# delete n nodes
27+
last_m_node.next= current_node
28+
29+
return head
30+
```
31+
32+
```java
33+
classSolution {
34+
publicListNodedeleteNodes(ListNodehead,intm,intn) {
35+
ListNode currentNode= head;
36+
ListNode lastMNode= head;
37+
38+
while (currentNode!=null) {
39+
// initialize mCount to m and nCount to n
40+
int mCount= m, nCount= n;
41+
42+
// traverse m nodes
43+
while (currentNode!=null&& mCount!=0) {
44+
lastMNode= currentNode;
45+
currentNode= currentNode.next;
46+
mCount--;
47+
}
48+
49+
// traverse n nodes
50+
while (currentNode!=null&& nCount!=0) {
51+
currentNode= currentNode.next;
52+
nCount--;
53+
}
54+
55+
// delete n nodes
56+
lastMNode.next= currentNode;
57+
}
58+
59+
return head;
60+
}
61+
}
62+
```
63+
64+
```cpp
65+
classSolution {
66+
public:
67+
ListNode* deleteNodes(ListNode* head, int m, int n) {
68+
ListNode* currentNode = head;
69+
ListNode* lastMNode = head;
70+
71+
while (currentNode != nullptr) {
72+
// initialize mCount to m and nCount to n
73+
int mCount = m, nCount = n;
74+
75+
// traverse m nodes
76+
while (currentNode != nullptr && mCount != 0) {
77+
lastMNode = currentNode;
78+
currentNode = currentNode->next;
79+
mCount--;
80+
}
81+
82+
// traverse n nodes
83+
while (currentNode !=nullptr && nCount !=0) {
84+
currentNode = currentNode->next;
85+
nCount--;
86+
}
87+
88+
// delete n nodes
89+
lastMNode->next = currentNode;
90+
}
91+
92+
return head;
93+
}
94+
};
95+
```
96+
97+
```javascript
98+
classSolution {
99+
/**
100+
*@param{ListNode}head
101+
*@param{number}m
102+
*@param{number}n
103+
*@return{ListNode}
104+
*/
105+
deleteNodes(head,m,n) {
106+
let currentNode= head;
107+
let lastMNode= head;
108+
109+
while (currentNode!==null) {
110+
// initialize mCount to m and nCount to n
111+
let mCount= m, nCount= n;
112+
113+
// traverse m nodes
114+
while (currentNode!==null&& mCount!==0) {
115+
lastMNode= currentNode;
116+
currentNode=currentNode.next;
117+
mCount--;
118+
}
119+
120+
// traverse n nodes
121+
while (currentNode!==null&& nCount!==0) {
122+
currentNode=currentNode.next;
123+
nCount--;
124+
}
125+
126+
// delete n nodes
127+
lastMNode.next= currentNode;
128+
}
129+
130+
return head;
131+
}
132+
}
133+
```
134+
135+
::tabs-end
136+
137+
###Time & Space Complexity
138+
139+
- Time complexity: $O(N)$
140+
- Space complexity: $O(1)$
141+
142+
> Where $N$ is the length of the linked list pointed by`head`.
Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
##1. Two-Pointers Iteration
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
definsert(self,head:'Node',insertVal:int) ->'Node':
8+
9+
if head==None:
10+
newNode= Node(insertVal,None)
11+
newNode.next= newNode
12+
return newNode
13+
14+
prev, curr= head, head.next
15+
toInsert=False
16+
17+
whileTrue:
18+
19+
if prev.val<= insertVal<= curr.val:
20+
# Case #1.
21+
toInsert=True
22+
elif prev.val> curr.val:
23+
# Case #2. where we locate the tail element
24+
# 'prev' points to the tail, i.e. the largest element!
25+
if insertVal>= prev.valor insertVal<= curr.val:
26+
toInsert=True
27+
28+
if toInsert:
29+
prev.next= Node(insertVal, curr)
30+
# mission accomplished
31+
return head
32+
33+
prev, curr= curr, curr.next
34+
# loop condition
35+
if prev== head:
36+
break
37+
# Case #3.
38+
# did not insert the node in the loop
39+
prev.next= Node(insertVal, curr)
40+
return head
41+
```
42+
43+
```java
44+
classSolution {
45+
publicNodeinsert(Nodehead,intinsertVal) {
46+
if (head==null) {
47+
Node newNode=newNode(insertVal,null);
48+
newNode.next= newNode;
49+
return newNode;
50+
}
51+
52+
Node prev= head;
53+
Node curr= head.next;
54+
boolean toInsert=false;
55+
56+
do {
57+
if (prev.val<= insertVal&& insertVal<= curr.val) {
58+
// Case 1
59+
toInsert=true;
60+
}elseif (prev.val> curr.val) {
61+
// Case 2
62+
if (insertVal>= prev.val|| insertVal<= curr.val)
63+
toInsert=true;
64+
}
65+
66+
if (toInsert) {
67+
prev.next=newNode(insertVal, curr);
68+
return head;
69+
}
70+
71+
prev= curr;
72+
curr= curr.next;
73+
}while (prev!= head);
74+
75+
// Case 3
76+
prev.next=newNode(insertVal, curr);
77+
return head;
78+
}
79+
}
80+
```
81+
82+
```cpp
83+
classSolution {
84+
public:
85+
Node* insert(Node* head, int insertVal) {
86+
if (head == nullptr) {
87+
Node* newNode = new Node(insertVal, nullptr);
88+
newNode->next = newNode;
89+
return newNode;
90+
}
91+
92+
Node* prev = head;
93+
Node* curr = head->next;
94+
bool toInsert = false;
95+
96+
do {
97+
if (prev->val <= insertVal && insertVal <= curr->val) {
98+
// Case 1
99+
toInsert = true;
100+
} else if (prev->val > curr->val) {
101+
// Case 2
102+
if (insertVal >= prev->val || insertVal <= curr->val)
103+
toInsert = true;
104+
}
105+
106+
if (toInsert) {
107+
prev->next = new Node(insertVal, curr);
108+
return head;
109+
}
110+
111+
prev = curr;
112+
curr = curr->next;
113+
} while (prev != head);
114+
115+
// Case 3
116+
prev->next = new Node(insertVal, curr);
117+
return head;
118+
}
119+
};
120+
```
121+
122+
```javascript
123+
class Solution {
124+
/**
125+
* @param {_Node} head
126+
* @param {number} insertVal
127+
* @return {_Node}
128+
*/
129+
insert(head, insertVal) {
130+
if (head === null) {
131+
let newNode = new _Node(insertVal, null);
132+
newNode.next = newNode;
133+
return newNode;
134+
}
135+
136+
let prev = head;
137+
let curr = head.next;
138+
let toInsert = false;
139+
140+
do {
141+
if (prev.val <= insertVal && insertVal <= curr.val) {
142+
// Case 1
143+
toInsert = true;
144+
} else if (prev.val > curr.val) {
145+
// Case 2
146+
if (insertVal >= prev.val || insertVal <= curr.val)
147+
toInsert = true;
148+
}
149+
150+
if (toInsert) {
151+
prev.next = new _Node(insertVal, curr);
152+
return head;
153+
}
154+
155+
prev = curr;
156+
curr = curr.next;
157+
} while (prev !== head);
158+
159+
// Case 3
160+
prev.next = new _Node(insertVal, curr);
161+
return head;
162+
}
163+
}
164+
```
165+
166+
::tabs-end
167+
168+
###Time & Space Complexity
169+
170+
- Time complexity: $O(N)$
171+
- Space complexity: $O(1)$
172+
173+
> Where $N$ is the size of the list.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp