[leetcode]Swap Nodes in Pairs

新博文地址：[leetcode]Swap Nodes in Pairs

http://oj.leetcode.com/problems/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.

 转换相邻节点的前后次序

要求：空间复杂度O(1)，不能改变ListNode的值

好吧，暂时无视这些要求：

1. 如果可以改变ListNode的值，程序会非常简单：直接交换节点与后继节点的值即可

	public ListNode swapPairsWithModifyValues(ListNode head) {
		ListNode tail = head;
		while (tail != null) {
			if (tail.next != null) {
				int tem = tail.val;
				tail.val = tail.next.val;
				tail.next.val = tem;
				tail = tail.next.next;
			} else {
				break;
			}
		}
		return head;
	}

 2. 如果可以分配空间，需要借助栈来实现，也是相当简单的：（由于只需要转置2个节点，因此栈空间开到2就可以了）

public ListNode swapPairsWithExtraSpace(ListNode head) {
		if (head == null) {
			return null;
		}
		Stack stack = new Stack<ListNode>();
		ListNode tail = head;
		ListNode newHead = new ListNode(0);
		ListNode newTail = newHead;
		while (tail != null) {
			stack.push(tail);
			tail = tail.next;
			if (tail != null) {
				stack.push(tail);
				tail = tail.next;
				newTail.next = new ListNode(((ListNode) stack.pop()).val);
				newTail = newTail.next;
			}
			newTail.next = new ListNode(((ListNode) stack.pop()).val);
			newTail = newTail.next;
		}
		return newHead.next;
	}

 3. 无空间，不修改节点值的做法，需要维护四个指针，这个大家画个图就出来了，解释起来比较麻烦。。。（太没节操了。。。）

	public ListNode swapPairs(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode preHead = new ListNode(0, head);
		ListNode node = head.next;
		ListNode prePre = preHead;
		ListNode pre = head;
		while (node != null) {
			ListNode post = node.next;
			node.next = pre;
			pre.next = post;
			prePre.next = node;
			
			if(post == null){
				break;
			}
			prePre = pre;
			node = post.next;
			pre = post;
			if(node == null){
				break;
			}
			post = node.next;
		}
		return preHead.next;
	}