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