DAY5 - 链表(一)

链表算是常出的题型之一吧(?
今天先整理出相对直观好理解的题目，明天补上比较需要思考的
链表也不需要多介绍了，直接上题目整理

例题实战

206.反转链表
这个应该是讲到烂了..但还是写一下吧

[法一]迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            return head;
        }
        //2->1->3
        //2<-1<-3
        ListNode* f = nullptr, *c = head, *c_next = head->next;
        while(c){
            c_next = c->next;
            c->next = f;
            f = c;
            c = c_next;
        }
        return f;
    }
};

[法二] 递回

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            return head;
        }
        //2-> 1<-3<-5
        //1<-3<-5<-2
        ListNode* new_head = reverseList(head->next);//返回子链的head节点
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    }
};

21.合并有序链表
这题在排序的文章中讲过了，就不写了

160.相交链表
这题很有趣，从两端开始走，走到底就到另一端的头部，最後相遇就是交点!!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==nullptr||headB==nullptr){
            return nullptr;
        }
        ListNode* pA = headA, *pB = headB;
        while(pA!=pB){
            pA = pA==nullptr?headB:pA->next;
            pB = pB==nullptr?headA:pB->next;
        }
        return pA;
    }
};