511. Swap Two Nodes in LinkedList

Leave a comment

September 4, 2016 by oneOokay

这题有tricky的部分需要考虑到:

  • swap的nodes可能出去linked list的头或尾
  • swap的nodes可能是相邻的两个nodes,也可能是不相邻的。
  • 可能只找到一个node

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @param head a ListNode
* @oaram v1 an integer
* @param v2 an integer
* @return a new head of singly-linked list
*/
public ListNode swapNodes(ListNode head, int v1, int v2) {
if(v1 == v2 || head == null || head.next == null)
return head;

ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy; //这里也可以直接ListNode cur = dummy.
ListNode pre1 = null;
ListNode pre2 = null;
while (head.next != null) {
if (head.next.val == v1) {
pre1 = head;
}else if (head.next.val == v2) {
pre2 = head;
}
if (pre1 != null && pre2 != null) {
break;
}
head = head.next;
}

if (pre1 == null || pre2 == null) { //当没有同时找到v1和v2时,直接return
return dummy.next;
}

if (pre2.next == pre1) { //确保pre1在pre2之前,
ListNode t = pre1;
pre1 = pre2;
pre2 = t;
}
ListNode node1 = pre1.next;
ListNode node2 = pre2.next;
ListNode after2 = node2.next;
if (pre1.next == pre2) { //处理swap的nodes为相邻的node时
pre1.next = node2;
node2.next = node1;
node1.next = after2;
}else {
pre1.next = node2;
node2.next = node1.next;
pre2.next = node1;
node1.next = after2;
}

return dummy.next;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: