[LeetCode]143. Reorder List / python , java

https://leetcode.com/problems/reorder-list/

Reorder List - LeetCode

 

 

   예시 ) 1 -> 2 -> 3 -> 4 ->  5 -> 6 과 같은 linked list가 주어진다면, 

     1 -> 6 -> 2 -> 5 -> 3 -> 4 과 같이 처음과 마지막 을 순차적으로 연결시켜서 반환해주면 된다. 

 

 위의 문제는 3가지의 순서대로 푼다. 

 

1. linked list를 반으로 잘라준다. 

2. 반으로 자른 뒷부분을 뒤집어준다. 

3. 앞부분의 리스트와 뒷 부분의 리스트를 재조합 해주면 된다. 

 

 

 

파이썬 풀이 

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


class Solution:
    def reorderList(self, head: ListNode) -> None:
    if not head:
    	return 
 
#1.연결리스트를 반으로 잘라준다. 
#slow와 fast가 동시에 출발하는데, fast는 slow보다 딱 두배 먼저 간다.
#따라서, fast가 끝나는 순간 slow는 리스트 절반 위치에 위치하게 된다. 
    slow = fast = head #slow, fast는 head가 가르키는 곳을 참조. 
    while fast and fast.next:
    	slow = slow.next 
        fast = fast.next.next
     
#2.뒷 부분을 리버스해준다. 
#convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4
	prev, curr = None, slow
    while curr:
    	curr.next, prev, curr = prev, curr, curr.next
        
#3.앞 + 뒷 머지해준다.
#merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4
	first, second = head, prev
    while second.next:
    	first.next, first = second, first.next
        second.next, second = first, second.next

 

 

 

자바 풀이

public static void reorderList(ListNode head) { // array int[]
    if (head == null) return;

    ListNode slow = head;
    ListNode fast = head;

    // 1. 반 짜르고
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    ListNode prev = null, curr = slow, next;
    // 1 -> 2 -> 3 -> null
    // null <- 1 <- 2 <- 3
    // 3 -> 2 -> 1 -> null
    // 2. 반짜르고 뒷부분 리버스
    while (curr != null) {
        next = curr.next;

        curr.next = prev;

        prev = curr;
        curr = next;
    }

    // 1 -> 2 -> 3
    // 6 -> 5 -> 4

    // 3. 앞부분 + 뒷부분 재조합
    ListNode first = head, second = prev;
    while (second.next != null) {
        next = first.next;
        first.next = second;
        first = next;

        next = second.next;
        second.next = first;
        second = next;
    }
}