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.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode p1 = head, p2 = head.next, p = new ListNode(0);
head = p2;
while (p1 != null && p2 != null) {
p.next = p2;
p1.next = p2.next;
p2.next = p1;
p = p1;
p1 = p1.next;
if (p1 == null)
return head;
p2 = p1.next;
if (p2 == null)
return head;
}
return head;
}
}
大清早在实验室卡到了p=p1那个位置,最开始我没有考虑交换之后第二个元素变到前面来了需要一个引用指向交换前的前面一个元素,不然链断开了就接不上了。考虑到这个之后,我就new了一个p来记录交换完了的最后一个位置,没交换的就可以利用这个接上去了,但是这个p=p.next其实还是指向的p2。后来才意识到,换成p=p1就正确了。
再去看看人家写的程序,确实简单有效。
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null && head.next.next != null) {
ListNode n1 = head.next, n2 = head.next.next;
// head->n1->n2->...
// => head->n2->n1->...
head.next = n2;
n1.next = n2.next;
n2.next = n1;
// move to next pair
head = n1;
}
return dummy.next;
}
可以把判断全都丢给while,机智