Swap Nodes in Pairs
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.
Solution: The power of recursion
My first solution is not recursive, yet it is not only bug-prone, but also hard to follow.
My first solution is not recursive, yet it is not only bug-prone, but also hard to follow.
/** * 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 p = head; head = head.next; ListNode tail = null; while (p != null && p.next != null) { ListNode q = p.next; ListNode r = q.next; q.next = p; p.next = r; if (tail != null) { tail.next = q; } tail = p; p = r; } return head; } }
/** * 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 p = head, q = head.next, r = q.next; q.next = p; p.next = swapPairs(r); return q; } }
No comments:
Post a Comment