leetcode刷题指南
19. Remove Nth Node From End of List
用fast和slow两个指针 ,fast比slow快n个节点 ,再同时移动,则fast.next==null时,slow为要删除节点的上一个(要删除节点,必须要有删除节点的上一个节点的指针,所以走到这里停下)
有可能删除的是正数的第一个节点,所以 fast和slow的初始值为start, start=new ListNode(0);start.next=head;
因为head有可能已经被删,所以最终返回start.next;(正数第0个节点)
160.
Intersection of Two Linked Lists
第一次遍历:得出a和b的长度之差n
第二次遍历:长的链表指针向前移动n,然后逐个比较,不相等且不为空则前进,退出循环后,如果指针为空,则说明到最后都不相等,返回Null;如果不为空,则返回该指针,即为第一个相等的位置。
21.
Merge Two Sorted Lists
默认都是升序的链表
迭代:
生成新节点head=listNode(0),res=head ,(head.next指向l1或l2)常用方法,在结果链表前生成一个节点指向这个节点,方便对头结点的处理和结果链表的返回。
如果l1.val<l2.val 且非空 head.next=l1
否则 head.next=l2
并且 head=head.next;
如果 此时有一个链表非空(剩下的都是大数),则接在head之后,最后返回res.next
递归:
class
Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
return merge(l1,l2);
}
public ListNode merge(ListNode l1,ListNode l2){
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
if(l1.val<l2.val){
l1.next=merge(l1.next,l2);
return l1;
}
else{
l2.next=merge(l1,l2.next);
return l2;
}
}
}
141.
Linked List Cycle
算法的核心思想是两个指针同时移动,快的是慢的两倍,如果有环,不管环连接的位置,快的指针一定会和慢的指针在某一处相遇,这个作为退出循环的条件,返回true。如果没有环,指针一定会在某一处走到null,因此退出循环,返回false
328.
Odd Even Linked List
第一次没看答案。。。。
我的思路:生成一个新链表res,odd=head,指针每次移动两下,到结尾,复制节点连接到res上。even=head.next.再来一次循环,指针每次移动两下,到结尾,复制节点连接到res上。
讨论:odd.next=odd.next.next
even.next=exen.next.next 相当于在原链表进行指针转移
odd=odd.next
even=even.next
最后odd.next=evenHead(偶数的头)
148.
Sort List
排序链表,最快的方法,归并排序
归并的思想,先分治,再合并。
分治与合并都是递归的思想
归并:合并两个升序的数组,比较两个值,将小的留下来.next,剩下的部分继续归并
分治:将链表分为两半,对每一半分别排序。
138.
Copy List with Random Pointer
48. Rotate Image
不能运用新的空间,只能在原矩阵进行交换,所以,要进行两次交换,先沿着对角线1\2,再沿着中轴线1|2。
注意:写交换的循环之时,不应该i=0;length j=0;length因为这样会把换后的结果又交换回来,变成原来的结果。因此,沿着对角线交换,主要考虑上三角 i=0;length j=i;length 。沿着中轴线交换,考虑左半边,i=0;length j=0;length/2