`
huntfor
  • 浏览: 194190 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[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;
	}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics