SwapPairs 문제

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Subscribe to see which companies asked this question

해석 : 연결된 목록이 있으면 인접한 두 노드를 서로 바꾸고 head를 반환하십시오.

예를 들어, 1-> 2-> 3-> 4가 주어지면 목록을 2-> 1-> 4-> 3으로 돌려 보내야합니다.

알고리즘은 일정한 공간만 사용해야합니다. 목록의 값은 수정할 수 없으며 노드 자체만 변경할 수 있습니다.

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}

public class Solution {
	static ListNode swapPairs(ListNode head) {
		//현재 노드가 null이거나 다음 노드가 null인 경우
        if(head == null || head.next == null){
        	return head;
        }
        
        ListNode cur = head; //현재 노드
        ListNode newHead = head.next; //반환하는 노드
        
        //현재 노드가 null이거나 다음 노드가 null일 때까지
        //ex) 1 -> 2 -> 3 -> 4 |  [ ] cur, ( ) tmp 
        while(cur != null && cur.next != null){
            ListNode tmp = cur; //1번 노드(임시 노드), (1) -> 2 -> 3 -> 4
            cur = cur.next; //2번 노드로 이동, (1) -> [2] -> 3 -> 4
            tmp.next = cur.next; // (1) -> 3 -> 4
            					 // [2] ->
            cur.next = tmp;      // [2] -> (1) -> 3 -> 4
            cur = tmp.next;		 // 2 -> (1) -> [3] -> 4
            
            //현재 노드가 null이 아니고, 다음 노드도 null이 아니면
            if(cur != null && cur.next != null){
            	tmp.next = cur.next;// 2 -> 1 -> (3) -> [4]
            }
        }
        return newHead;
    }

	public static void main(String[] args) {
		ListNode a = new ListNode(1);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(3);
		ListNode d = new ListNode(4);
		
		a.next = b;
		b.next = c;
		c.next = d;
		
		ListNode node = swapPairs(a);
		
		while(node != null){
			System.out.print(node.val + " ");
			node = node.next;
		}
	}
}

난이도 : Easy

위와 같은 문제를 풀기 위해서는 단방향 연결리스트의 개념과 연결리스트의 Swap 지식이 필요하다.