链表有关的题

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

你一个链表，删除链表的倒数第 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode x;
        x.next = head;
        ListNode* p1 = &x;
        ListNode* p2 = p1;
        int cnt = 0;
        while(cnt!=n){
            cnt ++;
            p1 = p1->next;
        }
        while(p1->next){
            p1 = p1->next;
            p2 = p2->next;
        }
        p2->next = p2->next->next;
        return x.next;
    }
};

截屏2021-11-17 上午1.23.46.png

---

LC21 合并两个有序链表
https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        if(l1->val < l2->val ) {l1->next = mergeTwoLists(l1->next, l2);
        return l1;}
        else{ l2->next = mergeTwoLists(l1, l2->next);
        return l2;}    
    }
};

---

LC61 61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(head==nullptr || k==0) return head;
        ListNode *p1, *p2, *new_head;
        p1 = head;
        p2 = head;
        int length = 0;
        while(p1->next){
            length ++;
            p1 = p1->next;
        }
        length++;
        p1 = head;
        for(int i=0; i < k%length; ++i){
            p1 = p1->next;
        }
        while(p1 && p1->next){
            p2 = p2->next;
            p1 = p1->next;
        }
        new_head = p2->next?p2->next:head;
        p1->next = head;
        p2->next = nullptr;
        return new_head;

    }
};

---

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

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(head==nullptr) return head;
        ListNode* p = head;
        while(p->next && p!=nullptr)
        {
            if(p->next->val == p->val) p->next = p->next->next;
            else p = p->next;
        }
        return head;
    }
};

截屏2021-11-17 上午1.43.55.png

---

LC160 160. 相交链表

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

/**
 * 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 == NULL || headB == NULL) return NULL;
        ListNode *p1, *p2;
        p1 = headA;
        p2 = headB;
        int length_diff = 0;
        while(p1 != NULL){
            p1 = p1->next;
            length_diff ++;
        }
        while(p2 != NULL){
            p2 = p2->next;
            length_diff --;
        }
        if(length_diff>0){
            while(length_diff>0){
                headA = headA->next;
                length_diff --;
            }
        }
        else{
            while(length_diff<0){
                headB = headB->next;
                length_diff ++;
            }
        }
        while(headB != NULL){
                if(headA == headB) return headA;
                headA = headA->next;
                headB = headB->next;
            }
        return NULL;
    }
};