第1周 数据结构-链表

Leetcode 题解 - 链表

• 找出两个链表的交点 160. Intersection of Two Linked Lists (Easy)
• 链表反转 206. Reverse Linked List(Easy)
• 归并两个有序的链表 21. Merge Two Sorted Lists(Easy)
• 从有序链表中删除重复节点 83. Remove Duplicates from Sorted List(Easy)
• 删除链表的倒数第 n 个节点 19. Remove Nth Node From End of List（Medium）

找出两个链表的交点

本题总结：链表问题中需要找交点或是找环等题目可以使用双指针将问题转换为追及问题进行求解。
扩展：判断链表是否有环并找到环的入口

class Solution {
public:
    // ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    //     /*
    //     思路：遍历链表A，记录下所有结点，再遍历链表B，遇到的第一个出现在链表A中的节点就是第一个公共节点
    //     时间复杂度: O(n)
    //     空间复杂度：O(n)
    //     */
    //     set<ListNode*> Aset;
    //     while(headA != NULL){
    //         Aset.insert(headA);
    //         headA = headA->next;
    //     }
    //     while(headB != NULL){
    //         if(Aset.count(headB) > 0)
    //             return headB;
    //         headB = headB->next;
    //     }
    //     return NULL;
    // }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        /*
        思路：循环遍历，假设链表A为a+c，a为非共享部分，c为共享部分，链表B的长度为b+c，在遍历一次完成后两个指针的路程分别为a+c和b+c，如果此时将遍历A和B的指针进行互换（用遍历A的指针取遍历B，B的去遍历A），那么接下来两个指针的路程分别为b,a后两个指针的路程均达到a+b+c，则此时两个指针会相遇。恰好这里需要再走的路程b,a就是链表B和链表A的非共享部分长度，所以两个指针一定会相遇在第一个共享节点。如果两个链表没有共享部分，则它们不会相遇，但会在路程为a+b后同时为NULL。
        时间复杂度: O(n)
        空间复杂度：O(1)
        */
        ListNode* pA = headA, *pB = headB;
        while(pA != pB){
            if(pA == NULL)
                pA = headB;
            else
                pA = pA->next;
            if(pB == NULL)
                pB = headA;
            else
                pB = pB->next; 
        }
        return pA;
    }
};

链表反转

本题注意使用迭代式进行反转时要注意先保存下next后再对next进行更改，否则会导致无法获取当前节点的next节点。递归式需要注意，在对node进行反转后node必为反转后的链表的最后一个节点，所以对head->next反转后，得到的反转后的链表必定以head->next节点为结尾，只需要将head链到它之后即可。

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
        /*
        思路：递归式，得到反转以head->next的结果后再把head链到最后
        时间复杂度：O(n)
        空间复杂度：O(1)
        */
        if(head == NULL)
            return head;
        ListNode* revHead = reverseList(head->next);
        if(revHead == NULL)
            return head;
        else{
            head->next->next = head;
            head->next = NULL;
            return revHead;
        }
        // 时间复杂度O(n^2)
        // ListNode* temp = revHead;
        // if(temp != NULL){
        //     while(temp->next != NULL)
        //         temp = temp->next;
        //     temp->next = head;
        //     head->next = NULL;
        //     return revHead;
        // }
        // else
        //     return head;
    }
//    ListNode* reverseList(ListNode* head) {
//         /*
//         思路：迭代式，逐个反转，注意先将next存下来后再操作
//         时间复杂度：O(n)
//         空间复杂度：O(1)
//         */
//         ListNode* revHead = NULL;
//         while(head != NULL){
//             ListNode* nextCopy = head->next;
//             head->next = revHead;
//             revHead = head;
//             head = nextCopy;
//         }
//         return revHead;
//     }

归并两个有序链表

为了方便设置一个伪头节点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        /*
        思路：逐个元素比较，先取两个链表头部较小的值，然后逐步next
        时间复杂度：O(n)
        空间复杂度：O(1)
        */
        ListNode node = ListNode(0);
        ListNode* headCopy = &node, *head=&node;
        while(l1 != NULL || l2 != NULL){
            if(l1 == NULL){
                head->next = l2;
                break;
            }
            else if(l2 == NULL){
                head->next = l1;
                break;
            }
            else if(l1->val < l2->val){
                head->next = l1;
                l1 = l1->next;
            }
            else{
                head->next = l2;
                l2 = l2->next;
            }
            head = head->next;
        }
        return headCopy->next;
    }
};

从有序链表中删除重复节点

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        /*
        思路：遇到和当前节点值不一样节点才next
        时间复杂度：O(n)
        空间复杂度：O(1)
        */
        ListNode* headCopy = head;
        while(head != NULL){
            ListNode* temp = head->next;
            while(temp != NULL && temp->val == head->val)
                temp = temp->next;
            head->next = temp;
            head = head->next;
        }
        return headCopy;
    }
};

删除链表的倒数第 n 个节点

双指针+伪头节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        /*
        思路：双指针法，头尾指针在链表中以相同速度移动，移动过程中距离永远为n+1，这样ptail到NULL的时候，phead刚好为要删除的节点的前一个节点，这时只需删除phead的next节点即可
        时间复杂度：O(n)
        空间复杂度：O(1)
        */
        ListNode newHead = ListNode(0);   // phead的目标是成为要被删除的节点的前一个节点，如果要删除的节点是第一个节点则需要一个伪节点做它的前节点
        ListNode* phead = &newHead, *ptail = &newHead, *headCopy = &newHead;
        phead->next = head;
        while(n >= 0) {
            ptail = ptail->next;
            n -= 1;
        }
        while(ptail != NULL){
            phead = phead->next;
            ptail = ptail->next;
        }
        phead->next = phead->next->next;
        return headCopy->next;
    }
};