leetcode刷题详解二

本质上是走过自己的路，再走过对方的路，这是求两个链表相交的方法

 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//本质上是走过自己的路，再走过对方的路if(headA == NULL|| headB == NULL){return NULL;}ListNode* temp_a = headA;ListNode* temp_b = headB;while(temp_a!=temp_b){if(temp_a == NULL){temp_a = headB;}else{temp_a = temp_a->next;}if(temp_b == NULL){temp_b = headA;}else{temp_b = temp_b->next;}}return temp_a;}

双指针法

情况一：两个链表相交。这个好判断

情况二：两个链表不相交。由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，指针pA 移动了m+n 次、指针pB 移动了 n+m 次之后，两个指针会同时变成空值null，此时返回null，满足循环条件。

ListNode* reverseList(ListNode* head) {if(head == nullptr){return head;}if(head->next == nullptr){return head;}ListNode *temp = reverseList(head->next);head->next->next = head;head->next = nullptr;return temp;}

上面这段代码是反转列表标准递归代码，也很好理解

使用迭代好理解。这道题第一反应就是四种种情况，全是空，一个是空，全不为空。

正常理解就是if，else if什么的，但是这样在写全不为空的时候很麻烦。

下面代码一个while(l1 && l2)就解决了上面的问题，很巧妙，很值得记住。必须全不为空才能进入循环，有一个是空指针就不能进入，这样代码好写很多很多

ListNode *head = new ListNode(-1);ListNode *pre = head;while(l1 && l2){ListNode* temp1 = l1;ListNode* temp2 = l2;if(l1->val >= l2->val){pre->next = l2;l2 = l2->next;}else{pre->next =l1;l1 = l1->next;}pre = pre->next;}if(l1 == nullptr){pre->next = l2;}if(l2 ==nullptr){pre->next = l1;}return head->next;}

思路：用快慢指针，如果是环形链表会相交

主要点在于while的循环条件，一定要针对快指针进行条件判断同时用&&而不是||

bool hasCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;if(head == nullptr || head->next == nullptr){return false;}while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;if(fast == slow){return true;}}return false;}

这道题自己画图就知道了，本质就是一道数学题。

1. 判断有无环

2. 

   a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

   即a=c

3. 当第一次相遇时，快指针回到头结点，慢指针不动。两个指针按照相同速度走，相遇点即为环的入口点。

ListNode *detectCycle(ListNode *head) {ListNode* slow = head;        ListNode* fast = head;        while(fast && fast->next){           slow = slow->next;            fast = fast->next->next;            if(slow == fast){                fast = head;                while(fast != slow){                    fast = fast->next;                    slow = slow->next;                }                return fast;            }        }        return nullptr;    
}

当碰到链表第几个节点的时候，双指针的思想可能正合适。

我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

ListNode* removeNthFromEnd(ListNode* head, int n) {        //双指针思想，以后这种倒数的长度类型的题目都可以用双指针        ListNode* p = head;        ListNode* q = head;       while(n>0){            p = p->next;            n--;        }        if(!p){            return head->next;        }        while(p->next){            p = p->next;            q = q->next;        }        q->next = q->next->next;       return head;    
}

思路：交换节点的题，就要有temp->next和temp->next->next。

如果 temp 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。否则，获得 temp 后面的两个节点 node1(temp->next)和 node2(temp->next->next)，通过更新节点的指针关系实现两两交换节点。

下面是错误代码

ListNode* swapPairs(ListNode* head) {        ListNode* temp = new ListNode(-1);        temp->next = head;        while(temp->next&&temp->next->next){           ListNode* l1 = temp->next;           ListNode* l2 = temp->next->next;           temp->next = l2;           l1->next =l2->next;           l2->next = l1;           temp = l1;        }        return head;    
}

输入：1,2,3,4

输出：1,4,3

错误原因：注意这道题head节点指的是首节点！这是最重要一点。其次，最开始head节点为1，在上面代码交换结束后正常来说为2,1,4,3，但是，head节点此刻还是1，如果返回head，则2被漏掉

正确代码

ListNode* swapPairs(ListNode* head) {        ListNode* temp = new ListNode(-1);        temp->next = head;       ListNode* dummy = temp;        while(temp->next&&temp->next->next){           ListNode* l1 = temp->next;           ListNode* l2 = temp->next->next;           temp->next = l2;           l1->next =l2->next;           l2->next = l1;           temp = l1;        }        return dummy->next;    
}