链表随机节点

问题描述

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

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

思路

• 首先，将链表存到一个一维数组中
• 然后，int n=tmp.size();return tmp[random()%n]即可

题解

class Solution {
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    vector<int> tmp;
    Solution(ListNode *head) {
        ListNode *p=head;
        while (p){
            tmp.push_back(p->val);
            p=p->next;
        }
    }

    /** Returns a random node's value. */
    int getRandom() {
        int n=tmp.size();
        return tmp[random()%n];
    }
};

分隔链表

问题描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

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

思路

借助了两个vector。

• 若是链表为空：直接返回nullptr即可。
• 链表不为空：遍历链表的过程中，将节点值小于x的存到一个vector中，将值大于等于x的存到一个vector中。
• 利用两个vector生成两个链表。

• 根据不同情况将两个链表拼接起来。

  小于x的链表为空，那么返回大于x链表的头节点即可
  大于等于x的链表为空，那么返回小于x链表的头节点即可
  两个都不空，将大于等于x的链表拼接到小于x的链表的后面
  两个链表都为空，即链表为空，在最开始特判过了。

题解

class Solution {
public:
    vector<int> tmp1;
    vector<int> tmp2;
    ListNode *head1;
    ListNode *head2;
    ListNode *ret;
    ListNode *buildList(vector<int> vec, ListNode *&node) {
        int n = vec.size();
        ListNode *p = nullptr;
        for (int i = 0; i < n; i++) {
            if (p == nullptr) {
                p = new ListNode(vec[i]);
                node = p;
            } else {
                p->next = new ListNode(vec[i]);
                p = p->next;
            }
        }
        return node;
    }

    ListNode *partition(ListNode *head, int x) {
        if (head == nullptr)
            return nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            if (cur->val < x) tmp1.push_back(cur->val);
            else tmp2.push_back(cur->val);
            cur = cur->next;
        }
        int n1=tmp1.size();
        int n2 =tmp2.size();
        if(n1!=0) head1=buildList(tmp1,head1);
        if(n2!=0) head2=buildList(tmp2,head2);
        if(n1==0&&n2!=0) ret = head2;
        else if(n2==0&&n1!=0) ret =  head1;
        else {
            ListNode *tail=head1;
            while (tail->next!= nullptr){
                tail=tail->next;
            }
            tail->next=head2;
            ret = head1;
        }
        return ret;
    }
};

给单链表加一

问题描述

你可以假设这个整数除了 0 本身，没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:
输入: [1,2,3]
输出: [1,2,4]

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

思路

从链表的最后一个节点开始，找到第一个不为9的位置

• 如果整个链表都为9，那么将原链表的节点的值都置为0，并在链表前加一个值为1的节点。
• 如果链表存在不为9的节点，该节点前边的节点值不变，该节点的值+1，该节点后边的值置为0。

题解

class Solution {
public:
    ListNode *plusOne(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        int location = -1;
        for (int i = vec.size() - 1; i >= 0; i--) {
            if (vec[i] != 9) {
                location = i;
                break;
            }
        }
        if (location == -1) {
            ListNode *tmphead = new ListNode(1);
            ListNode *tmp = head;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
            tmphead->next = head;
            head = tmphead;
        } else {
            ListNode *tmp = head;
            int count = 0;
            while (count <location) {
                tmp = tmp->next;
                count++;
            }
            tmp->val = tmp->val + 1;
            tmp = tmp->next;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
        }

        return head;
    }
};

排序链表

问题描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

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

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

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

思路

• 遍历链表，将链表存在一个int类型的vector中。
• 对链表进行排序。
• 根据vector重新建立一个链表。

题解

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        if(vec.size()==0)
            return nullptr;
        sort(vec.begin(),vec.end());
        ListNode *q = nullptr;
        ListNode *ret;
        for (int i = 0; i < vec.size(); i++) {
            if (q == nullptr) {
                q = new ListNode(vec[i]);
                ret=q;

            } else {
                q->next = new ListNode(vec[i]);
                q = q->next;
            }
        }
        return ret;
    }
};

旋转链表

问题描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

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

思路

• 首先将链表存到vector vec中。
• 对特殊情况进行判断，链表为空，vec.size()==0) return nullptr，向右移动0步，直接return head
• 按照题目要求，将移动后的元素存到一个新的vector tmp中
• 根据tmp建立一个新的链表，并返回其头节点

题解

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        vector<int> vec;
        ListNode *cur = head;
        while (cur != nullptr) {
            vec.push_back(cur->val);
            cur = cur->next;
        }
        if(vec.size()==0)  return nullptr;
        if(k==0) return head;
        k = k % (vec.size());
        vector<int> tmp;
        for (int i = vec.size()-k; i < vec.size(); i++) {
            tmp.push_back(vec[i]);
        }
        for (int i = 0; i <vec.size()-k; i++) {
            tmp.push_back(vec[i]);
        }
        ListNode *p = nullptr;
        ListNode *newnode;
        for (int i = 0; i < tmp.size(); i++) {
            if (p == nullptr) {
                p=new ListNode(tmp[i]);
                newnode=p;
            } else{
                p->next= new ListNode(tmp[i]);
                p=p->next;
            }
        }
        return newnode;
    }
};