[파이썬 알고리즘] 8장 - 역순 연결리스트 2 (leetcode 92)

https://leetcode.com/problems/reverse-linked-list-ii/

Reverse Linked List II - LeetCode

 

<문제>

인덱스 m에서 n까지를 역순으로 만들어라.
인덱스 m은 1부터 시작한다

 

<예시>

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

 

 

---

def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:
    if head is None:
        return None
    
    dummy_head = ListNode()  # 길이 1인 linked list 들어왔을 때 오류 방지하기 위하여
    dummy_head.next = head

    # m-1 index의 노드에 도착
    cur = dummy_head
    for _ in range(m-1):
        cur = cur.next

    first_node = cur.next
    last_node = cur.next.next
    for _ in range(n-m):
        cur.next, last_node, cur.next.next = last_node, last_node.next, cur.next
    first_node.next = last_node  # first node와 last node 연결

    return dummy_head.next

 

 

 

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

으로 만드는 것을 예제로 설명을 진행하겠다.

 

cur node는 항상 m-1 index의 노드이다.

cur.next, last_node, cur.next.next = last_node, last_node.next, cur.next를 수행해준다

• cur.next = last_node : cur_node(1)의 다음 노드가 last_node(3)가 된다 
• last_node = last_node.next : 3 node가 2 node를 가리킬 것이므로 3->2 링크를 잃어버리기 전 3의 다음 노드를 저장해준다
• cur.next.next = cur.next : 3 node가 2 node을 가리키도록 해준다

 

cur node는 항상 m-1 index의 노드이다.

cur.next, last_node, cur.next.next = last_node, last_node.next, cur.next를 수행해준다

• cur.next = last_node : cur_node(1) 의 다음 노드가 last_node(4)가 된다
• last_node = last_node.next : 4 node가 3 node를 가리키게 되면서 4->5 링크를 잃어버린다.
  이 링크를 잃어버리면 영영 5 node에 접근할 수 없으므로 4 node의 다음 노드(5)를 다른 변수에 저장해준다
• cur.next.next = cur.next : 4 node가 3 node를 가리키도록 해준다

 

 

 

마지막으로 m index의 노드가 n+1 index의 node를 가리키도록 변경하면 끝이다