Given a linked list, swap every two adjacent nodes and return its head.
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.
Solution
(Swap-Nodes-in-Pairs.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* 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) {
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
prev.next = head;
if(head==null || head.next==null)
return head;
while (prev.next!=null && prev.next.next!=null){
ListNode first = prev.next;
ListNode second = prev.next.next;
first.next = second.next;
prev.next = second;
prev.next.next = first;
prev = prev.next.next;
}
return dummy.next;
}
}
|
(Swap-Nodes-in-Pairs.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
front = head
end = front.next
prev = ListNode(-1)
prev.next = head
newhead = head.next
while end!=None:
nextNode = end.next
front.next = nextNode
end.next = front
prev.next = end
if nextNode == None:
break
prev = front
front = nextNode
end = front.next
return newhead
|