链表必刷题第一部分

枫长...大约 17 分钟

206.反转链表open in new window

给你单链表的头节点head，请你反转链表，并返回反转后的链表。

解题思路一：迭代法

迭代方法的关键在于使用三个指针（prev, curr, next）来遍历链表，依次修改指针的指向。详细步骤如下：

  1. 初始化三个指针：prev 指向空（null），curr 指向链表头部，next 指向空（null）。
  2. 遍历链表：
    • 在每一次迭代中，首先将 curr 的下一个节点保存到 next。
    • 然后修改 curr 的下一个节点指向 prev，实现反转。
    • 更新 prev 和 curr 指针，将它们向前移动一个节点。
    • 重复这个过程直到 curr 为空。
  3. 当迭代结束时，prev 指向反转后的链表头部。

解题思路二：递归法

递归方法的关键在于从最后一个节点开始反转，并且在递归过程中修改指针的指向。详细步骤如下：

  1. 如果当前节点（head）为空或者其下一个节点为空，直接返回当前节点（递归的基本情况）。
  2. 反转从当前节点的下一个节点开始的子链表，并将返回的新头部赋值给 new_head。
  3. 修改当前节点的下一个节点的指向为当前节点，即 head.next.next = head。
  4. 将当前节点的下一个节点设为空，即 head.next = null。
  5. 返回新的头部节点 new_head。
// 迭代法
ListNode* reverseList(ListNode* head) {
    ListNode *cur = head, *pre = nullptr, *next = nullptr;
    while(cur != nullptr) {
        next = cur-> next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

// 递归法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* new_head = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return new_head;
    }
};

83.删除排序链表中的重复元素open in new window

给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

解题思路一：迭代法

删除排序链表中的重复元素的思路是遍历链表，并比较相邻的节点，如果两个相邻节点的值相同，则删除其中一个。详细步骤如下：

  1. 初始化一个指针 curr 指向链表头部。
  2. 遍历链表：
    • 比较 curr 节点和 curr 的下一个节点的值：
      • 如果值相同，则将 curr 的下一个节点指向下一个的下一个节点（即删除 curr 的下一个节点）。
      • 如果值不同，则将 curr 指针向前移动一个节点。
    • 重复这个过程直到 curr 或者 curr 的下一个节点为空。
  3. 返回链表头部节点。

解题思路二：递归法

递归删除排序链表中的重复元素的思路是将问题分解为两部分：首先处理头节点及其重复元素，然后递归处理剩余链表。这种方法的关键在于利用递归处理子链表，并将结果链接到当前节点。详细步骤如下：

  1. 递归的基本情况：如果链表为空（head 为 None）或者链表只有一个节点（head.next 为 None），直接返回 head。
  2. 递归调用：将 head.next 传递给递归函数，将返回的结果赋值给 head.next。
  3. 比较当前节点（head）和其下一个节点（head.next）的值：
    • 如果值相同，说明存在重复元素，此时将当前节点的下一个节点指向下一个的下一个节点（即删除 head 的下一个节点），并保持当前节点不变。
    • 如果值不同，说明不存在重复元素，直接返回当前节点。
  4. 返回链表头部节点。
//迭代法
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* curr = head;

        while (curr != nullptr && curr->next != nullptr) {
            if (curr->val == curr->next->val) {
                curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }

        return head;
    }
};

// 递归法
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        head->next = deleteDuplicates(head->next);

        if (head->val == head->next->val) {
            head = head->next;
        }

        return head;
    }
};

25.K个一组翻转链表open in new window

给你链表的头节点head，每k个节点一组进行翻转，请你返回修改后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

解题思路

将链表中的每 k 个节点分为一组，然后对每组进行翻转，可以用迭代和递归两种方式，迭代法的代价较小，更推荐迭代法。

解题思路一：迭代法

代码的主要思路是将链表分为已翻转部分、待翻转部分和未处理部分。我们遍历整个链表，每次取待翻转部分的k个节点进行翻转，然后将翻转后的部分连接到已翻转部分的尾部。若最后一组节点数量不足k个，则不翻转。

  1. 首先，检查输入的链表是否为空或k是否为1。如果满足这些条件，则不需要翻转链表，直接返回head即可。
  2. 创建一个虚拟节点（dummy）并将其next指针指向链表的头节点。这个虚拟节点有助于处理边界条件，使代码更简洁。
  3. 初始化prev、curr和temp三个指针，分别表示已翻转部分的尾节点、待翻转部分的头节点和临时节点。
  4. 遍历链表，统计链表的长度。
  5. 使用while循环处理链表。当链表剩余的节点数大于等于k时，进入循环。
  6. 在循环内，我们需要翻转k个节点。通过一个for循环，迭代k-1次。
    • 将临时指针temp指向待翻转部分的第二个节点。
    • 更新curr的next指针，使其跳过temp。
    • 将temp插入到prev和prev->next之间，完成翻转操作。
    • 更新prev的next指针，指向temp。
  7. 完成一组k个节点的翻转后，更新prev为已翻转部分的新尾节点（即curr）。
  8. 更新curr指针，使其指向未处理部分的头节点。
  9. 减少链表的剩余长度（count -= k）。
  10. 当所有节点都处理完毕时，返回虚拟节点（dummy）的next指针，即翻转后链表的头节点。

解题思路二：递归法

使用递归的方法，并且不需要预先计算链表的长度。详细步骤如下：

  • 遍历链表，使用 cur 指针前进 k 步。如果在达到 k 步之前遇到链表末尾（即 cur == nil），说明剩余节点不足 k 个，直接返回 head，保持原有顺序。
  • 调用 reverse 函数翻转当前分组，该函数接受两个参数：分组的起始节点 head 和分组的结束节点的下一个节点 cur。翻转后的链表头部为 newHead。
  • 递归调用 reverseKGroup 函数处理剩余的链表。将翻转后的当前分组的尾节点（即原始 head 节点）的 Next 指针指向递归调用的结果。
  • 返回翻转后的链表头部节点 newHead。
// 迭代法
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *prev = &dummy, *curr = head, *temp;
        int count = 0;
        while (head) {
            count++;
            head = head->next;
        }
        while (count >= k) {
            for (int i = 1; i < k; i++) {
                temp = curr->next;
                curr->next = temp->next;
                temp->next = prev->next;
                prev->next = temp;
            }
            prev = curr;
            curr = prev->next;
            count -= k;
        }
        return dummy.next;
    }
};

// 递归法
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        int count = 0;
        while (cur != nullptr && count < k) {
            cur = cur->next;
            count++;
        }
        if (count == k) {
            ListNode* newHead = reverse(head, cur);
            head->next = reverseKGroup(cur, k);
            return newHead;
        }
        return head;
    }

    ListNode* reverse(ListNode* start, ListNode* end) {
        ListNode* prev = nullptr, *curr = start;
        while (curr != end) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

160.相交链表open in new window

给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

解题思路

可以采用双指针的方法。详细步骤如下：

  1. 初始化两个指针 pA 和 pB，分别指向链表 headA 和 headB 的头节点。
  2. 同时遍历两个链表，当指针 pA和 pB都到达末尾时，它们走过的路径长度相等。如果链表相交，它们会在相交节点相遇；如果链表不相交，它们会在末尾节点null相遇。
    • 遍历过程中，如果 pA 到达链表末尾，将其重置为链表 headB 的头节点；如果 pB 到达链表末尾，将其重置为链表 headA 的头节点。
    • 这样，当 pA 和 pB 再次到达链表末尾时，它们走过的节点数相等，且它们所经过的末尾部分节点完全相同。因此，如果链表相交，它们会在相交节点相遇；如果链表不相交，它们会在末尾节点（null）相遇。
  3. 返回相交节点或 null。
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //双指针思路
        ListNode* a = headA;
        ListNode* b = headB;
        while(a! = nullptr || b! = nullptr){
            if(a == nullptr) a = headB;
            if(b == nullptr) b = headA;
            if(a == b) return a;
            a = a->next;
            b = b->next;
        }
        return nullptr;
    }

21.合并两个有序链表open in new window

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路

可以采用双指针的方法。详细步骤如下：

  1. 创建一个虚拟头节点 dummy，并创建一个指针 cur 指向虚拟头节点。cur 将用于构建新的合并后的链表。

  2. 初始化两个指针 p1 和 p2，分别指向两个升序链表 headA 和 headB 的头节点。

  3. 当 p1 和 p2 都不为 null时，执行以下操作：

    • 比较 p1 和 p2 节点的值。

      • 如果 p1.val <= p2.val，将 cur 的 next 指针指向 p1，然后将 p1 指针前进一步。
      • 如果 p1.val > p2.val，将 cur 的 next 指针指向 p2，然后将 p2 指针前进一步。

    • 将 cur 指针前进一步，指向新添加的节点。

  4. 当循环结束时，至少有一个链表已经遍历完。将未遍历完的链表（如果有）的剩余部分连接到 cur 的 next 指针上。

  5. 返回虚拟头节点的下一个节点，即为合并后的链表头节点。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* cur = &dummy;
        ListNode* p1 = list1, *p2 = list2;
        while (p1 != nullptr && p2 != nullptr) {
            if (p1->val <= p2->val) {
                cur->next = p1;
                p1 = p1->next;
            } else {
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        cur->next = p1 != nullptr ? p1 : p2;
        return dummy.next;
    }
};

143.重排链表open in new window

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → L~n - 1~ → Ln 请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路

这道题实际是三道题目综合：

  1. 找到链表的中点：
    • 使用快慢指针法，创建两个指针 slow 和 fast，初始时都指向链表头节点 head。
    • 同时移动这两个指针，slow 指针每次移动一步，fast 指针每次移动两步。当 fast 指针到达链表尾部时，slow 指针恰好位于链表的中点。
  2. 反转链表的后半部分：
    • 从中点节点 slow 开始，将链表后半部分反转。可以使用迭代或递归方法进行反转。
    • 反转后，slow 指针指向新的子链表头节点。
  3. 合并两个链表：
    • 初始化两个指针 p1 和 p2，分别指向原始链表的头节点 head 和反转后链表的头节点 slow。
    • 依次从两个链表中取出一个节点，将它们按照题目要求的顺序连接起来。
    • 不断重复上述过程，直到两个链表中的节点都被连接完毕。
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return;
        }

        // 找到链表中点并将后半部分链表翻转
        ListNode *slow = head, *fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = nullptr;
        mid = reverse(mid);

        // 将前半部分链表和翻转后的后半部分链表交替合并
        ListNode *p1 = head, *p2 = mid;
        while(p1 != nullptr && p2 != nullptr) {
            ListNode *tmp1 = p1->next, *tmp2 = p2->next;
            p1->next = p2;
            p2->next = tmp1;
            p1 = tmp1;
            p2 = tmp2;
        }
    }

private:
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr, *next = nullptr;
        ListNode* cur = head;
        while(cur != nullptr) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

148.排序链表open in new window

给你链表的头结点head，请将其按 升序 排列并返回 排序后的链表 。

解题思路

数组的排序都很熟悉，有快排，归并排序，堆排这三种思路，但这三种方法不一定都适合链表排序，快排和堆排实现都需要通过数组下标访问元素，而这点链表做不到。可以使用归并排序算法。详细步骤如下：

分割链表

  • 使用快慢指针法找到链表的中点：创建两个指针 slow 和 fast，初始时都指向链表头节点 head。同时移动这两个指针，slow 指针每次移动一步，fast 指针每次移动两步。当 fast 指针到达链表尾部时，slow 指针恰好位于链表的中点。
  • 断开链表：将链表从中点处分成两个子链表。为此，创建一个新的指针 prev，初始化为 None。在遍历链表时，将 prev 的 next 指针设置为 None，从而断开链表。

递归排序子链表

  • 对于每个子链表，递归执行归并排序。递归的基本情况是链表长度为 1 或 0，此时链表已经是有序的，直接返回。

合并子链表

  • 使用双指针法合并两个有序子链表。创建两个指针 p1 和 p2，分别指向两个子链表的头节点。同时遍历两个子链表，将较小的节点加入新链表，并更新相应的指针。
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
    
    ListNode* findMid(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;
        
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        if (prev) prev->next = nullptr;
        return slow;
    }
    
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* mid = findMid(head);
        ListNode* l1 = sortList(head);
        ListNode* l2 = sortList(mid);
        
        return merge(l1, l2);
    }
};
你认为这篇文章怎么样？
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.8