[LeetCode]024. Swap Nodes in Pairs
1822 ワード
Given a linked list, swap every two adjacent nodes and return its head.
For example, Given
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
Solution: draw a graph, 1->2->3->4, and then find the relationship.
Running time: O(n);
Note: Create the top node to reference the head; create the node pre to express the connection.
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.
Solution: draw a graph, 1->2->3->4, and then find the relationship.
Running time: O(n);
Note: Create the top node to reference the head; create the node pre to express the connection.
/**
* 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) {
// Start typing your Java solution below
// DO NOT write main() function
if(head == null || head.next == null){
return head;
}
ListNode cur = head;
ListNode top = null;
ListNode pre = null;
while(cur.next != null){
ListNode first = cur;
ListNode second = first.next;
first.next = second.next;
second.next = first;
// use a top reference point to the head node;
if(top == null){
top = second;
}
//use a pre reference to express the pre and after relationship: testcase: (1,2,3,4)
if(pre == null){
pre = first;
}else{
pre.next = second;
pre = first;
}
if(first.next == null){
break;
}else{
cur = first.next;
}
}
return top;
}
}