오늘의 리트코드 (3)

21. Merge Two Sorted Lists

# Definition for singly-linked list.

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        
        head = ListNode(-1)
        cursor = head
        
        while l1 != None and l2 != None :
            #l1 or l2 의 next로 계속 이동하기 때문에 마지막 노드에 다다른 것 = 현재 노드가 None일 경우이기 때문에 while조건을 이렇게 걸어주었다.
            if l1.val < l2.val :
                cursor.next = l1
                l1 = l1.next
            else : 
                cursor.next = l2
                l2 = l2.next
            # 비교하여 작은 값을 가진 링크드 리스트일 경우 먼저 cursor가 가리키도록 했다. 
            # 이미 비교가 끝나 cursor가 가리켰다면 다시는 그 값을 가리킬 필요 없게 다음값을 가리키도록 한다. (링크드리스트의 순회를 생각하면 된다)
            
            cursor = cursor.next
            
        if l1 == None :
            cursor.next = l2 
        else :
             cursor.next = l1
                
        
        return head.next
            
        
        

링크드 리스트에 대한 기본적인 이해를 확인하는 문제이다.
문제에 대한 해결방법은 주석을 확인하길 바란다.

206. Reverse Linked List

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        prev_node = None
        
        
        while head != None :
            if prev_node :
                node = ListNode(head.val,prev_node)
                prev_node = node
            else :
                prev_node = ListNode(head.val)
                
            head = head.next            
    
        return prev_node

코드를 대략적으로 설명하자면 위의 그림과 같은데 (글씨체가 ㅎㅎ;)

prev를 초기에는 None으로 설정하여 아무것도 없음을 알려준다.
이는 이전의 노드를 알수없는 첫번째 노드를 순회할때 첫번째 노드를 순회한다고 알려주는 용도이다.

prev에 첫번째 노드의 값을 가진 노드로 만든다. prev는 None을 가리키도록 한다.

두번째 노드부터 prev에 담긴값을 이용하여 prev를 늘려갈것이다.
처음에는 두번째 노드에 있는 값을 None을 가리키는 노드로 만든 후 next 값은 prev_node로 해준다.
이렇게 만든 노드는 새로운 prev_node가 된다.

즉 2->1 / 3->4->5
이렇게 두개의 링크드 리스트가 있는 셈이 된다.

이러한 루프를 반복하는 방식으로 구현하면 된다.

876. Middle of the Linked List

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        temp = head
        cnt = 0
        
        while temp != None :
            temp = temp.next
            cnt +=1
        
        for i in range(0,(int(cnt)/2)):
            head = head.next
            
        return head
            

간단한 문제, temp를 이용하여 주어진 링크드 리스트를 건들이지 않고 링크드 리스트의 길이를 잰 다음 중앙에 해당하는 부분까지 head 값을 받을 수 있도록 루프문을 구성하여 head를 리턴해주었다.