[Leetcode] 연결리스트
- For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: The above figure represents the given linked list. The indices of the nodes are written below. Since n = 7, node 3 with value 7 is the middle node, which is marked in red. We return the new list after removing this node. ** **Example 2:
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: The above figure represents the given linked list. For n = 4, node 2 with value 3 is the middle node, which is marked in red. ** **Example 3:
- The number of nodes in the list is in the range [1, 105].
- 1 **5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
# 1. 길이 구하기
length = 0
current = head
while current:
length += 1
current = current.next
middle_index = length // 2
# 2. 중간 노드의 이전 노드까지 이동
current = head
for i in range(middle_index - 1):
current = current.next
# 3. 중간 노드 삭제 (포인터 연결 수정)
current.next = current.next.next
return head
다음은 투 포인터 설정 방법. 공간복잡도 O(1), 시간복잡도 O(n) 투 포인터로 한 번에 중간점 도달 가능
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 엣지 케이스: 노드가 1개뿐인 경우
if not head or not head.next:
return None
# 투 포인터 설정
slow = head
fast = head
prev = None
# fast가 끝에 도달할 때까지 이동
# slow는 한 번에 한 칸, fast는 한 번에 두 칸
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
# slow가 중간 노드를 가리키므로 삭제
prev.next = slow.next
return head
- 단일 포인터 + 이전 노드 추적
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def removeElements(self, head, val):
# 더미 노드로 헤드 제거 케이스 처리
dummy = ListNode(0)
dummy.next = head
prev = dummy
current = head
while current:
if current.val == val:
prev.next = current.next # 제거
else:
prev = current # 이전 노드 갱신
current = current.next
return dummy.next
- 재귀적 접근
1
2
3
4
5
6
def removeElements(self, head, val):
if not head:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else head
재귀가 가독성이 더 좋지만 호출비용이 커서 오버헤드가 있다.
328. Odd Even Linked List Solved Medium Topics [
](#) Companies Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input. You must solve the problem in O(1) extra space complexity and O(n) time complexity.
Example 1:
Input: head = [1,2,3,4,5] Output: [1,3,5,2,4] Example 2:
- The number of nodes in the linked list is in the range [0, 104].
- -106 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
# 홀수와 짝수 체인의 시작점
odd = head # 1번째 노드 (홀수)
even = head.next # 2번째 노드 (짝수)
even_head = even # 짝수 체인의 헤드 저장
# 홀수는 홀수끼리, 짝수는 짝수끼리 연결
while even and even.next:
odd.next = even.next # 홀수 → 다음 홀수
odd = odd.next # 홀수 포인터 이동
even.next = odd.next # 짝수 → 다음 짝수
even = even.next # 짝수 포인터 이동
# 홀수 체인 끝에 짝수 체인 연결
odd.next = even_head
return head
## 동작 과정
'''
초기: [1] -> [2] -> [3] -> [4] -> [5]
odd even
1단계: odd.next = even.next → [1] -> [3] -> [4] -> [5]
[2] -> [4] -> [5]
2단계: even.next = odd.next → [1] -> [3] -> [5]
[2] -> [4]
최종: odd.next = even_head → [1] -> [3] -> [5] -> [2] -> [4]
'''