Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q17

Q17 Swap Nodes in Pairs

Q

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Sample Input

image

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Input: head = []
Output: []

Input: head = [1]
Output: [1]

Constraints

  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100

1. My own Solution

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

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        node = head
        
        #filtering the case when only 0 or 1 node.
        if not node or not node.next: 
            return node

        #<----after this line, the list is swappable---->

        #pointing #2 node, because second one will be the head.
        head_node = ListNode(0, node.next) 
        prev = ListNode() #just init.

        #loop while inswappable
        while node and node.next:
            prev.next = node.next #to change prev
            temp = node
            node = node.next
            temp.next = node.next
            node.next = temp
            prev = temp #to save the prev node
            print(node.val, temp.val)
            node = node.next.next
        
        return head_node.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#to test, you have to make to linked-list manually. 
inp1= [1,2,3,4, 5,6,7,8,9]
def makeLinkedList(inp: List) -> ListNode: 
    #function that create linked-list from the list
    node = ListNode()
    head = node
    for val in inp:
        new_node = ListNode(val)
        new_node.next = node.next
        node.next = new_node
        node = node.next
    return head

link1 = makeLinkedList(inp1).next

#for test
a = Solution()
head_node = a.swapPairs(link1)
while head_node:
    print(head_node.val)
    head_node = head_node.next

I solved it by myself… I’m so proud of myself understanding the structure of linked-list well. Let’s start from the while loop. Node-Swapping process is like this.

  1. Assign first node to the temp.
  2. Push the current node to the next node.
  3. Make temp point the next node of the current node.
  4. Make the current node point temp.
  5. Save temp to the prev, to save the address of the previous node.

Note that not just focus on the pair to swap, but also be aware of the previous node pointing the pair.

**보충 설명 : 이 문제에서 주의해야 할 점은 그저 pair을 스왑하면 끝나는 것이 아니라, 그 페어를 가르키는 “이전” 페어도 수정해주어야 한다는 것이다. 예를 들어 (앞 1, 2페어가 이미 스왑된) 2->1->3->4인 연결 리스트에서 4->3으로 바꾸었을 때 그 앞의 1이 4를 가르키도록 바꾸어야 한다.

2. Given Solution #1

1
2
3
4
5
6
7
8

def swapPairs(self, head: ListNode) -> ListNode:
    cur = head

    while cur and cur.next:
        cur.val, cur.next.val = cur.next.val, cur.val
        cur = cur.next.next

    return head

This is the method that only changes the values, not nodes themselves. So RESTRICTLY it is the wrong answer, since the problem requires to change the node itself.

3. Given Soltuion #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def swapPairs(self, head :ListNode) -> ListNode:
    root = prev = ListNode(None)
    prev.next = head

    while head and head.next:
        #assign to make b point a(head)
        b = head.next
        head.next = b.next
        b.next = head

        #assign to make prev point b
        prev.next = b

        #moves the nodes for the next comparison.
        head = head.next
        prev = prev.next.next
        
    return root.next

This solution is almost same with by answer, using iterative method. It’s pretty easy and already explained above, so I’ll skip explanations.

4. Given Soltuion #5

1
2
3
4
5
6
7

def swapPairs(self, head :ListNode) -> ListNode:
    if head and head.next:
        p = head.next
        head.next = self.swapPairs(p.next)
        p.next = head
        return p
    return head

By using recursion, you can make the codes shorten. It’s really sophisticated codes. By recursion, do swapping from the end and gradually swap forward. This process clearly solved bothersome problem that you need to make previous node point the swapped pair nodes. If not, prev node still points the (previously) front node, which is now at the back.

Overall Review

Designing algorithm itself is not that complicated. However, it’s easy to forget that there is more than just swapping pairs. You need to take care of both behind and after the pairs. This is not only limited to this problem, always remind of LINK between back and forth when solving linked-list problems.

참고