week2-链表复盘
Day 1: https://leetcode-cn.com/problems/design-linked-list/
采用单链表，然后试了js、C#两套代码执行通过，提交都没有通过，最后看了不通过的测试用例是因为插入了index=-1的元素，而题目中指出插入位置是0-index中之前插入，所以不清楚测试用例中[-1,0]是如何插入的
根据测试用例
["MyLinkedList","addAtHead","addAtTail","addAtHead","addAtTail","addAtHead","addAtHead","get","addAtHead","get","get","addAtTail"] [[],[7],[7],[9],[8],[6],[0],[5],[0],[2],[5],[4]]
输出
[null,null,null,null,null,null,null,-1,null,6,8,null]
预期结果
[null,null,null,null,null,null,null,8,null,6,7,null]
发现每次get都后移了一位，于是把p初始指向head，再执行代码
结果是[null,null,null,null,null,null,null,8,null,0,7,null] ，仍有一位不对，发现addAtHead一个节点后似乎一下增加了两个节点，这显然不可能，最后发现是尾节点没有再addAtTail后跟着赋值，增加rear=s;后所有取值又往前移了一位，所以之前的get方法没有问题改回。
public int Get(int index) {
int i=-1;
ListNode p = head;
while(p!=null){
if(++i == index){
return p.val;
}
p=p.next;
}
return -1;
}
public void AddAtTail(int val) {
ListNode s = new ListNode(val);
s.next = null;
rear.next = s;
rear = s; //忘记尾节点赋值
}
Day 2: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
这个相对简单，思路是拿当前节点的值和下一个节点比较，如果相同，node.next = node.next.next；如果不同，指针后移一位继续比较，需要注意判断比较的两个节点不能为null。
public class Solution {
public ListNode DeleteDuplicates(ListNode head) {
ListNode node = head;
while(node != null && node.next != null){
if(node.next.val == node.val){
node.next = node.next.next;
}else{
node = node.next;
}
}
return head;
}
}
Day 3：https://leetcode-cn.com/problems/merge-two-sorted-lists/
合并两个排序链表，分别从头开始取两个链表的头结点比较，返回较小节点值的链表指针，并将较小的节点往后移一位再次进行比较，是一个递归调用的过程，需要注意的是两个链表都可能为空的情况。
public class Solution {
public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val <l2.val){
l1.next = MergeTwoLists(l1.next, l2);
return l1;
}else{
l2.next =MergeTwoLists(l1, l2.next);
return l2;
}
}
}
Day 4: https://leetcode-cn.com/problems/reverse-linked-list/
反转相当于从不表节点的头结点开始按照addAtHead的方式插入新的链表
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode resHead = null;
while(head!=null){
ListNode newNode = head.next;
head.next = resHead;
resHead = head;
head = newNode;
}
return resHead;
}
}
Day5：https://leetcode-cn.com/problems/linked-list-cycle/
循环链表，原理就是快慢指针，就是在一个圆形跑道上，同一起点，跑的快的和跑的慢的肯定可以多次相遇
public class Solution {
public bool HasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(slow!=null && fast!=null && fast.next !=null){
slow=slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
Day 6：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
参考评论区的解法，计算出headA和headB中那个链表最长，计算出长度把长度较长的链表偏移，使两个链表对齐。最后同同时遍历两个链表，如果相等 说明它们相交了。
网友评论