LeetCode - Medium - 24. Swap Nodes in Pairs

╰半夏微凉° 2023-01-06 11:42 110阅读 0赞

## Topic ##

*  Linked List
 *  Recursion

## Description ##

[https://leetcode.com/problems/swap-nodes-in-pairs/][https_leetcode.com_problems_swap-nodes-in-pairs]

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

**Example 1**:

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

**Example 2**:

Input: head = []
    Output: []

**Example 3**:

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

**Constraints**:

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

**Follow up**: Can you solve the problem without modifying the values in the list’s nodes? (i.e., Only nodes themselves may be changed.)

## Analysis ##

方法一：迭代，两节点互换值val。

方法二：递归，连接点互换。

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class SwapNodesInPairs { 
    
    	// 方法一：
    	public ListNode swapPairs1(ListNode head) { 
    		ListNode p1 = head;
    
    		while (p1 != null) { 
    			ListNode p2 = p1.next;
    
    			if (p2 != null) { 
    				int temp = p1.val;
    				p1.val = p2.val;
    				p2.val = temp;
    				p1 = p1.next;
    			}
    			p1 = p1.next;
    		}
    
    		return head;
    	}
    
    	// 方法二：
    	public ListNode swapPairs2(ListNode node) { 
    		if (node == null || node.next == null)
    			return node;
    
    		ListNode next = node.next;
    		node.next = swapPairs2(next.next);
    		next.next = node;
    		return next;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.SinglyLinkedList.*;
    import org.junit.Test;
    
    
    public class SwapNodesInPairsTest { 
    
    	@Test
    	public void test() { 
    		SwapNodesInPairs obj = new SwapNodesInPairs();
    		
    		assertTrue(areTwoListEqual(obj.swapPairs1(ints2List(1, 2, 3, 4)), ints2List(2, 1, 4, 3)));
    		assertTrue(areTwoListEqual(obj.swapPairs1(ints2List(1, 2, 3, 4, 5)), ints2List(2, 1, 4, 3, 5)));
    		assertNull(obj.swapPairs1(null));
    		assertTrue(areTwoListEqual(obj.swapPairs1(ints2List(1)), ints2List(1)));
    		
    		assertTrue(areTwoListEqual(obj.swapPairs2(ints2List(1, 2, 3, 4)), ints2List(2, 1, 4, 3)));
    		assertTrue(areTwoListEqual(obj.swapPairs2(ints2List(1, 2, 3, 4, 5)), ints2List(2, 1, 4, 3, 5)));
    		assertNull(obj.swapPairs2(null));
    		assertTrue(areTwoListEqual(obj.swapPairs2(ints2List(1)), ints2List(1)));
    	}
    }

[https_leetcode.com_problems_swap-nodes-in-pairs]: https://leetcode.com/problems/swap-nodes-in-pairs/