0%

leetcode链表

发表于 2022-03-07 更新于 2022-07-21 分类于数据结构，链表， leetcode题目
本文字数： 11k 阅读时长 ≈ 10 分钟

【道德经·第十二章】五色令人目盲，五音令人耳聋，五味令人口爽，驰骋畋（tián）猎令人心发狂，难得之货令人行妨。是以圣人为腹不为目，故去彼取此。

链表结构定义

 // 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) {}
};

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *dummy = new ListNode(-1);
    dummy->next = head;

    ListNode *fast = head, *slow = dummy;
    for(int i = 1; i <= n; i++)
        fast = fast->next;
    
    while(fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    ListNode *t = slow->next;
    slow->next= slow->next->next;
    delete t;
    return dummy->next;
}

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
本题有两种解决思路，一种递归一种迭代，思路都很精巧，下面来一一介绍：

1、递归解法

ListNode* reverseList(ListNode* head) {
    // 链表为空；head指向尾结点
    if(head==nullptr || head->next==nullptr)
        return head;

    ListNode *newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr
    return newHead;
}

2、迭代解法

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr, *cur = head;
    while(cur) {
        LisNode *nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }

    return pre;
}

92. 反转链表 II

反转从位置left到位置right的链表节点。

1、递归解法

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if(left == 1) {
        return reverseN(head, right);
    }

    head->next = reverseBetween(head->next, left-1, right-1);
    return head;
}

ListNode *successor = nullptr;
ListNode* reverseN(ListNode* head, int n) {
    if(n == 1) {
        successor = head->next;
        return head;
    }

    ListNode *newHead = reverseN(head->next, n-1);
    head->next->next = head;
    head->next = successor;
    return newHead;
}

2、迭代解法（推荐）

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode *dummy = new ListNode(-1, head);
    ListNode *pre = dummy;

    for(int i = 1; i <= left-1; i++) 
        pre = pre->next;
    
    ListNode *cur = pre->next;
    for(int i = left; i < right; i++) {
        ListNode *t = cur->next;
        cur->next = t->next;
        t->next = pre->next;
        pre->next = t;
    }

    return dummy->next;
}

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *a = head, *b = head;
    for(int i = 0; i < k; i++) {
        if(b == nullptr) return a;
        b = b->next;
    }

    ListNode *newHead = revList(a, b);
    a->next = reverseKGroup(b, k);
    return newHead;
}

ListNode* revList(ListNode* a, ListNode* b) {
    ListNode *pre = nullptr, *cur = a;
    while(cur != b) {
        ListNode *nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }

    return pre;
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。

1、递归解法

ListNode *left = nullptr;
bool isPalindrome(ListNode* head) {
    left = head;
    return traverse(head);
}

bool traverse(ListNode* right) {
    if(right == nullptr) {
        return true;
    }
    
    bool res = traverse(right->next);
    res = res && (left->val == right->val);
    left = left->next;
    return res;
}

2、迭代解法

bool isPalindrome(ListNode* head) {
    if(head==nullptr || head->next==nullptr)
        return true;
    
    ListNode *fast = head, *slow = head;
    // 这里要注意，只有这样写，【1,2,3,4】slow会在2；【1,2,3,4,5】slow会在3
    while(fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode *right = slow->next, *left = head;
    slow->next = nullptr;
    
    right = revList(right);
    while(right != nullptr) {
        if(left->val != right->val) 
            return false;
        
        left = left->next;
        right = right->next;
    }
    
    return true;
}

ListNode* revList(ListNode* l) {
    ListNode *pre = nullptr, *cur = l;
    while(cur != nullptr) {
        ListNode* t = cur->next;
        cur->next = pre;
        pre = cur;
        cur = t;
    }
    
    return pre;
}

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode *dummy = new ListNode(-1, nullptr);
    ListNode *cur = dummy;

    while(list1 && list2) {
        if(list1->val < list2->val) {
            cur->next = list1;
            list1 = list1->next;
        } else {
            cur->next = list2;
            list2 = list2->next;
        }

        cur = cur->next;
    }

    if(list1) cur->next = list1;
    if(list2) cur->next = list2;

    return dummy->next;
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

bool hasCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;

        if(fast == slow) return true;
    }

    return false;
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

ListNode* middleNode(ListNode* head) {
    ListNode *fast = head;
    ListNode *slow = head;
    // 这里要注意，只有这样写，【1,2,3,4】slow会在3；【1,2,3,4,5】slow会在3
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

160. 相交链表

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

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || !headB) return nullptr;

    ListNode *pa = headA, *pb = headB;

    int la = length(headA);
    int lb = length(headB);
    if(la > lb) {
        int diff = la - lb;
        while(diff--) pa = pa->next;
    } else {
        int diff = lb - la;
        while(diff--) pb = pb->next;
    }

    while(pa && pb) {
        if(pa == pb) return pa;
        pa = pa->next;
        pb = pb->next;
    }

    return nullptr;

}

int length(ListNode* list) {
    int cnt = 0;
    ListNode* cur = list;
    while(cur) {
        cnt++;
        cur = cur->next;
    }
    return cnt;
}

445. 两数相加 II

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    l1 = revList(l1);
    l2 = revList(l2);
    
    ListNode *t = add(l1, l2);
    return revList(t);
}

ListNode* revList(ListNode* l) {
    ListNode *pre = nullptr, *cur = l;
    while(cur != nullptr) {
        ListNode *t = cur->next;
        cur->next = pre;
        pre = cur;
        cur = t;
    }
    
    return pre;
}

ListNode* add(ListNode* l1, ListNode* l2) {
    ListNode *dummy = new ListNode(-1), *cur = dummy;
    
    int carry = 0;
    while(l1 || l2 || carry) {
        int sum = (l1? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        carry = sum/10;
        sum = sum%10;
        
        cur->next = new ListNode(sum);
        cur = cur->next;
        
        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }
    
    return dummy->next;
}

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode *dummy = new ListNode(-1);
    ListNode *cur = dummy;

    priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
    for(auto node : lists) {
        if(node != nullptr) {
            pq.push(node);
        }   
    }

    while(!pq.empty()) {
        auto t = pq.top(); pq.pop();
        cur->next = t;
        cur = cur->next;
        if (cur->next) pq.push(cur->next);
    }

    return dummy->next;

}

struct cmp{
    bool operator() (ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

148. 排序链表

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

class Solution {
public:
      ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *slow = head, *fast = head, *pre = nullptr;
        while(fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        ListNode* half1 = sortList(head);
        ListNode* half2 = sortList(slow);
        return mergeList(half1, half2);
    }
    
    ListNode* mergeList(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return dummy->next;
    }  
};

剑指 Offer II 029. 排序的循环链表

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

Node* insert(Node* head, int val) {
    Node *node = new Node(val);
    
    if(head == nullptr) {
        head = node;
        head->next = head;
    } else if(head->next == head) {
        head->next = node;
        node->next = head;
    } else {
        helper(head, node);
    }
    
    return head;
}

void helper(Node* head, Node* node) {
    Node *cur = head, *next = head->next;
    Node *biggest = head;
    
    while(!(cur->val<=node->val && next->val>=node->val) && next!=head) {
        cur = next;
        next = next->next;
        if(cur->val >= biggest->val) {
            biggest = cur;
        }
    }
    
    if(cur->val<=node->val && next->val>=node->val) {
        cur->next = node;
        node->next= next;
    } else {
        node->next = biggest->next;
        biggest->next = node;
    }
    
}

328. 奇偶链表

定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

ListNode* oddEvenList(ListNode* head) {
    if(head == nullptr) {
        return head;
    }
    
    ListNode *evenHead = head->next;
    ListNode *odd = head, *even = evenHead;
    while(even && even->next) {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    
    odd->next = evenHead;
    return head;
}

143. 重排链表

L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为：L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

void reorderList(ListNode* head) {
    ListNode *slow = head, *fast = head;
    
    while(fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    
    ListNode *last = slow->next, *pre = nullptr;
    slow->next = nullptr;
    
    while(last != nullptr) {
        ListNode *t = last->next;
        last->next = pre;
        pre = last;
        last = t;
    }
    
    ListNode *left = head, *right = pre;
    while(left && right) {
        ListNode *lnext = left->next;
        ListNode *rnext = right->next;
        
        left->next = right;
        right->next = lnext;
        left = lnext;
        right = rnext;
    }
}

83. 删除排序链表中的重复元素

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

递归法

ListNode* deleteDuplicates(ListNode* head) {
    if(!head || !head->next) 
        return head;

    head->next = deleteDuplicates(head->next);
    return (head->val == head->next->val) ? head->next : head;
}

迭代法

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* cur = head;
    
    while(cur && cur->next) {
        if(cur->val == cur->next->val) {
            cur->next = cur->next->next;
        } else {
            cur = cur->next;
        }
    }

    return head;
}

82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头head，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。

ListNode* deleteDuplicates(ListNode* head) {
    if (!head || !head->next) 
        return head;
        
    ListNode *dummy = new ListNode(-1), *pre = dummy;
    dummy->next = head;
    
    while(pre->next) {
        ListNode *cur = pre->next;
        while(cur->next && cur->next->val==cur->val) {
            cur = cur->next;
        }
        
        if(cur != pre->next) pre->next = cur->next;
        else pre = pre->next;
    }
    
    return dummy->next;
}

位我上者，灿烂星空；道德律令，在我心中。

本文作者： 仰望星空
本文链接： https://sun-ld.github.io/posts/6854.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！