子涵算法第十二天
24. 两两交换链表中的节点
递归：
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode newhead = head.next;
head.next = swapPairs(newhead.next);
newhead.next = head;
return newhead;
}
}时间复杂度：O(
空间复杂度：O(N)
递归并不是“免费”的。每一次函数调用都会在内存中开辟一块区域，叫做栈帧，用来存储局部变量和返回地址。
迭代：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummynode = new ListNode(0);
dummynode.next = head;
ListNode temp = dummynode;
while(temp.next != null && temp.next.next != null){
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummynode.next;
}
}时间复杂度：O(N)
空间复杂度：O(1)
142. 环形链表 II
双指针（快慢指针）：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode ptr = head;
while(ptr != slow){
ptr = ptr.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}时间复杂度：O(N)
空间复杂度：O(1)
哈希表遍历：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
Set visited = new HashSet<>();
ListNode pos = head;
while(pos != null){
if(visited.contains(pos)){
return pos;
}
else{
visited.add(pos);
}
pos = pos.next;
}
return null;
}
} 时间复杂度：O(N)
空间复杂度：O(N)
