DS&A - 2. Data Structures - Lesson 1. Swap Nodes

[minimanimoh]

Problem Statement

Given a linked list, swap the two nodes present at position i and j. The positions are based on 0-based indexing.

Note: You have to swap the nodes and not just the values.

Example:

• linked_list = 3 4 5 2 6 1 9
• positions = 3 4
• output = 3 4 5 6 2 1 9

Explanation:

• The node at position 3 has the value 2
• The node at position 4 has the value 6
• Swapping these nodes will result in a final order of nodes of 3 4 5 6 2 1 9

def swap_nodes(head, left_index, right_index):

    # if both the indices are same
    if left_index == right_index:
        return head

    left_previous = None
    left_current = None

    right_previous = None
    right_current = None

    count = 0
    temp = head
    new_head = None

    # find out previous and current node at both the indices
    while temp is not None:
        if count == left_index:
            left_current = temp
        elif count == right_index:
            right_current = temp
            break

        if left_current is None:
            left_previous = temp
        right_previous = temp
        temp = temp.next
        count += 1

    right_previous.next = left_current
    temp = left_current.next
    left_current.next = right_current.next

    # if both the indices are next to each other
    if left_index != right_index:
        right_current.next = temp

    # if the node at first index is head of the original linked list
    if left_previous is None:
        new_head = right_current
    else:
        left_previous.next = right_current
        new_head = head

    return new_head

[minimanimoh]

jeeeeeez

[minimanimoh]

전반적으로 전혀 이해가 되지 않는다 일단 case를 4개로 나눈 건 알겠음..

1. case 1: if both indices are the same e.g. (1,1) => 이부분 coding line 이해감. 같으니까 바꿀 필요 없으니까 그냥 head 돌리면 됨
2. case 2: find out previous and current node at both the indices e.g. (3,6) => 여기서부터 이해가 안됨, count == left_index가 같다는 것이 무슨 뜻인지 잘 모르겠다.
   count = 0 이니까 0 == left_index의 숫자 라는건데...? 이거 이해 안되니까 밑에서부터 줄줄이 이해 안감
3. case 3: if both the indices are next to each other e.g. (1,2)
4. case 4: if the node at first index is head of the original linked list e.g. (0, 3)