Given a linked list, swap every two adjacent nodes and return its head.

For example,

Given

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.**Understand the problem:**

The problem gives a linked list, swap every two adjacent nodes and return its head. For e.g. For 1->2->3->4, swap 1 and 2, 3 and 4, return 2->1->4->3. There are two requirements in the problem: you could only use constant space. You cannot modify the value in the list, just change the nodes.

Let's take several examples to show the problem.

For a single node list, 1, return 1

For 1->2, return 2->1

For 1->2->3, return 2->1->3.

For 1->2->3->4->5, return 2->1->4->3->5

**Solution:**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode helper = new ListNode(0); helper.next = head; ListNode pre = helper; ListNode p = null; ListNode q = null; ListNode post = head; while (post != null) { p = post; q = post.next; if (q == null) break; post = post.next.next; pre.next = q; q.next = p; p.next = post; pre = p; } return helper.next; } }

**A Neat Solution:**

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode helper = new ListNode(0); helper.next = head; ListNode pre = helper; ListNode cur = pre.next; while (cur != null && cur.next != null) { pre.next = cur.next; cur.next = cur.next.next; pre.next.next = cur; pre = cur; cur = pre.next; } return helper.next; } }

**Update on 9/21/15:**

/** * 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 dummyNode = new ListNode(0); dummyNode.next = head; ListNode prev = dummyNode; ListNode curr = head; int count = 0; while (curr != null) { count++; if (count % 2 == 1) { curr = curr.next; } else { ListNode next = curr.next; curr.next = prev.next; prev.next.next = next; prev.next = curr; prev = curr.next; curr = next; } } return dummyNode.next; } }

## No comments:

## Post a Comment