问题描述
https://leetcode.com/problems/swap-nodes-in-pairs/
解决思路(2019-12-22)
- while curr.next.next != null && curr.next != null, swap the two node
- the specific steps of swap coded in the function. the node before the first node which need to be swaped also should be considered!!!
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curr = dummy;
while(curr.next != null && curr.next.next != null){
swap(curr);
curr = curr.next.next;
}
return dummy.next;
}
public void swap(ListNode curr){
ListNode temp = new ListNode(0);
temp = curr.next;
curr.next = temp.next;
temp.next = temp.next.next;
curr.next.next = temp;
}
}
复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
解决思路(2019-07-15)
重要的是学会如何交换两个节点。交换两个节点，涉及到的不仅有这两个，还涉及第一个节点之前的节点，具体看swap函数
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
//no node or no enough node need to be swap and then will get out of while
while(current.next != null && current.next.next != null){
swap(current);
current = current.next.next;
}
return dummy.next;
}
private void swap(ListNode pre){
//to swap to nodes
ListNode dummy = new ListNode(0);
dummy = pre.next;
pre.next = dummy.next;
dummy.next = dummy.next.next;
pre.next.next = dummy;
}
}
复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
