分类 链表 下的文章

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

问题描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:
输入: 1->1->1->2->3
输出: 2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

题解

    public static ListNode deleteDuplicates(ListNode head) {
        //baseCase
        if (head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next;
        //如果是这种情况
        //      1 --> 1 --> 1 --> 2 --> 3
        //     head  next
        //1.则需要移动next直到出现与当前head.value不相等的情况（含null）
        //2.并且此时的head已经不能要了，因为已经head是重复的节点
        //--------------else-------------
        //      1 --> 2 --> 3
        //     head  next
        //3.如果没有出现1的情况，则递归返回的节点就作为head的子节点
        if (head.value == next.value) {
            //1
            while (next != null && head.value == next.value) {
                next = next.next;
            }
            //2
            head = deleteDuplicates(next);
        } else {
            //3
            head.next = deleteDuplicates(next);
        }
        return head;
    }

来源：力扣
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/comments/
作者：落寒

反转链表 II

问题描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii

思路

思路比较简单。
将反转前的链表存在一个vector tmp1中，按照题目要求对tmp1进行反转。
根据反转后的tmp1建立一个新链表。

题解

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        int len = 0;
        if (head == nullptr) return nullptr;
        ListNode *p = head;
        vector<int> tmp1;
        ListNode *head1;
        while (p != nullptr) {
            len++;
            tmp1.push_back(p->val);
            p = p->next;
        }
        vector<int> tmp2(tmp1);
        int count = 0;
        for (int i = m-1; i <= n-1; i++) {
            tmp1[i] = tmp2[n-1 - count];
            count++;
        }
        ListNode *tmp= nullptr;
        for (int i = 0; i < len; i++) {
            if (tmp == nullptr) {
                tmp = new ListNode(tmp1[i]);
                head1 = tmp;
            } else {
                tmp->next = new ListNode(tmp1[i]);
                tmp = tmp->next;
            }
        }
        return head1;
    }
};

两两交换链表中的节点

问题描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

思路

递归的思想

题解

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(head== nullptr||head->next== nullptr) return  head;
        ListNode *p=head;
        ListNode *q=head->next;
        p->next=swapPairs(q->next); 
        q->next=p;
        return q;
    }
};

两数相加 II

问题描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii

思路

数字相加的时候是从链表的末端开始的，所以用栈将两个链表存储起来会比较合适。
和两数相加I的思路一样，将情况分为3种：
1、两个栈都不为空
2、栈1为空
3、栈2为空
将每次相加的结果取余，余数为低位，压入栈中，栈底就是sum的最低位。
进位为相加的结果/10。
需要注意的是进位也要参与每次的加法。

通过栈构建链表时，需要特别注意：

ListNode *ret 为要返回的头节点。
一定要先建立cur = new ListNode(tmp.top());再让 ret = cur;
否则，ret只有一个节点。

题解

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        stack<int> stack1;
        stack<int> stack2;
        stack<int> tmp;
        int addtion = 0;
        while (l1 != nullptr) {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            stack2.push(l2->val);
            l2 = l2->next;
        }
        while (!stack1.empty() || !stack2.empty()) {
            if (!stack1.empty() && !stack2.empty()) {
                tmp.push((stack1.top() + stack2.top() + addtion) % 10);
                addtion = (stack1.top() + stack2.top() + addtion) / 10;
                stack1.pop();
                stack2.pop();
            } else if (!stack1.empty()) {
                tmp.push((stack1.top() + addtion) % 10);
                addtion = (stack1.top() + addtion) / 10;
                stack1.pop();
            } else {
                tmp.push((stack2.top() + addtion) % 10);
                addtion = (stack2.top() + addtion) / 10;
                stack2.pop();
            }
        }
        ListNode *ret, *cur = nullptr;

        if (addtion == 1) {
            tmp.push(1);
        }
        while (!tmp.empty()) {
            if (cur == nullptr) {
                cur = new ListNode(tmp.top());
                ret = cur;
                tmp.pop();
            } else {
                cur->next = new ListNode(tmp.top());
                tmp.pop();
                cur = cur->next;
            }
        }
        return ret;
    }
};

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

问题描述

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

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

思路

本题中需要删除链表中的倒数第n个节点，因此，求出链表长度len后，将此问题转化为删除链表中第len1=len-n个节点。
问题转化后，就是一个简单的遍历加删除节点的问题。

题解

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        int len = 1;
        ListNode *p = head;
        while (p->next != nullptr) {
            len++;
            p = p->next;
        }
        int len1 = len - n;
        if(len1==0){
            return head->next;
        }
        else{
            Find(head, len1);
            return head;
        }
    }
    int lo = 1;
    void Find(ListNode *&node, int n) {
       ListNode *p=node;
       while (lo<n){
           lo++;
           p=p->next;
       }
       p->next=p->next->next;
    }
};
  1. 1
  2. 2
  3. 3