【算法】两两交换链表中的节点24

24. 两两交换链表中的节点 - 力扣（Leetcode）

//两两交换链表中的节点24
public class SwapNodesInPairs24 {
	public static void main (String[] args){
		ListNode head = initLinkedList(new int[]{1,2,3,4,5,6});
		printLinkedList(head);

		head = new solution().swapPairs02(head);
		printLinkedList(head);
	}
	public static ListNode initLinkedList(int[] nums){
    	ListNode head = new ListNode(nums[0]);
    	ListNode cur = head,node;
    	for(int i = 1; i < nums.length; i++){
    		node = new ListNode(nums[i]);
    		cur.next = node;
    		cur = node;
    	}
    	return head;
    }
    public static void printLinkedList(ListNode head){
    	ListNode cur = head;
    	while(cur != null){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }

}

class solution {
	//迭代法
	public ListNode swapPairs(ListNode head) {
		if (head == null || head.next == null) {
			//如果 head 为空或者只有一个节点
			return head;
		}
		ListNode cur = head;
		ListNode next = head.next;
		ListNode temp = swapPairs(next.next);

		next.next = cur;
		cur.next = temp;

		return next;
    }
	//虚拟头节点法
	public ListNode swapPairs02(ListNode head) {
		if (head == null || head.next == null) {
			//如果 head 为空或者只有一个节点
			return head;
		}
		ListNode dummy = new ListNode(-1,head);
		ListNode cur = dummy;
		ListNode first;
		ListNode second;
		ListNode temp;
		while (cur.next != null && cur.next.next != null){
			first = cur.next;
			second = cur.next.next;
			temp = cur.next.next.next;
			//开始交换
			cur.next = second;
			second.next = first;
			first.next = temp;
			cur = first;
		}
		return dummy.next;
    }
}

class ListNode {
	int val;
	ListNode next;
	public ListNode (){}
	public ListNode (int val){ 
		this.val = val;
	}  
	public ListNode (int val, ListNode next){ 
		this.val = val;
		this.next = next;
	} 
}