算法随想录第四天打卡|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交 ,142.环形链表II

发布于：2024-05-11 ⋅ 阅读:(138) ⋅ 点赞:(0)

24. 两两交换链表中的节点

用虚拟头结点，这样会方便很多。 

本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。

题目链接/文章讲解/视频讲解： 代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy_head=ListNode(next=head)
        current=dummy_head
        while current.next and current.next.next:
            temp=current.next
            temp1=current.next.next.next
            current.next=temp.next
            temp.next.next=temp
            temp.next=temp1
            current=current.next.next
        return dummy_head.next

C++

/**
 * 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* swapPairs(ListNode* head) {
        ListNode* dummy_head=new ListNode(0);
        dummy_head->next=head;
        ListNode* current=dummy_head;
        while (current->next && current->next->next){
            ListNode* temp1=current->next;
            ListNode* temp2=current->next->next->next;
            current->next=temp1->next;
            temp1->next->next=temp1;
            temp1->next=temp2;
            current=current->next->next;
        }
        ListNode* temp=dummy_head->next;
        delete dummy_head;
        return temp;
    }
};

总结

下次要把临时节点写在循环里面，作为一个变量放在外面显得代码量很多。

19.删除链表的倒数第N个节点

双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。

题目链接/文章讲解/视频讲解：代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head=ListNode(next=head)
        slow,fast=dummy_head,dummy_head
        for i in range(n):
            fast=fast.next
        while fast.next:
            fast=fast.next
            slow=slow.next
        slow.next=slow.next.next
        return dummy_head.next

C++

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head=new ListNode(0);
        dummy_head->next=head;
        ListNode* fast=dummy_head;
        ListNode* slow=dummy_head;
        for (int i=0;i<n;i++)fast=fast->next;
        while (fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummy_head->next;
    }
};

面试题 02.07

本题没有视频讲解，大家注意 数值相同，不代表指针相同。

题目链接/文章讲解：代码随想录

Python

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head=new ListNode(0);
        dummy_head->next=head;
        ListNode* fast=dummy_head;
        ListNode* slow=dummy_head;
        for (int i=0;i<n;i++)fast=fast->next;
        while (fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummy_head->next;
    }
};

C++

/**
 * 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) {
        ListNode* cura=headA;
        ListNode* curb=headB;
        int lena=0,lenb=0;
        while (cura){
            cura=cura->next;
            lena++;
        }
        while (curb){
            curb=curb->next;
            lenb++;
        }
        if (lena>lenb){
            for (int i=0;i<lena-lenb;i++)headA=headA->next;
        }else{
            for (int i=0;i<lenb-lena;i++)headB=headB->next;
        }
        while (headA){
            if (headA==headB) return headA;
            headA=headA->next;
            headB=headB->next;
        }
        return nullptr;
    }
};

142.环形链表II

算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。

题目链接/文章讲解/视频讲解：代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast,slow=head,head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if fast==slow: 
                slow=head
                while slow!=fast:
                    slow=slow.next
                    fast=fast.next
                return fast
        return None

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while (fast && fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if (fast==slow){
                slow=head;
                while (slow!=fast){
                    slow=slow->next;
                    fast=fast->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

总结

都还写出来了，没有忘记，说明一刷的时候掌握还行。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布