3、链表-爱代码爱编程

2020-11-14 标签: 算法 c++ leetcode分类: 算法分类

链表

第一部分

1.1 LeetCode 206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法一：迭代反转

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode *pre = NULL;
        ListNode *cur = head;
        while (cur != NULL) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

解法二：递归反转

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IKZstjhm-1605350637476)(C:\Users\Dong\AppData\Roaming\Typora\typora-user-images\image-20200922142616826.png)]

注：只需要一个指针（head）就可改变两个指针指向

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        //求解基本问题
        if (head == nullptr || head->next == nullptr)
            return head;
        //大问题变成小问题。。递归到底，把大问题分解成小问题
        ListNode *ans = reverseList(head->next);
        //小问题变成大问题。。从递归函数最底层函数，依次进行逻辑操作，返回给上层函数
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }
};

1.2 LeetCode *92. 反转链表 II

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

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

示例:

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iIUDyN52-1605350637480)(C:\Users\Dong\AppData\Roaming\Typora\typora-user-images\image-20200921090736620.png)]

解法一：迭代

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *next;

        for (int i = 1; i < m; ++i) {
            next = cur->next;
            pre = cur;
            cur = next;
        }
        ListNode *pre1 = pre;
        ListNode *cur1 = cur;

        for (int i = m; i <= n; i++) {
            next = cur->next;
            cur->next = pre;//第一个没必要，但是不影响结果
            pre = cur;
            cur = next;
        }

        if (pre1 != nullptr) {
            pre1->next = pre;
        } else {
            head = pre1;
        }
        cur1->next = cur;
        return head;
    }
};

解法二：递归

class Solution {
private:
    ListNode *successor = NULL; // 后驱节点
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    ListNode *reverseN(ListNode *head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head->next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode *last = reverseN(head->next, n - 1);
        head->next->next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head->next = successor;
        return last;
    }
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // base case
        if (m == 1) {
            return reverseN(head, n);
        }
        // 前进到反转的起点触发 base case
        head->next = reverseBetween(head->next, m - 1, n - 1);
        return head;
    }
};

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

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

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

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

解法一：

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == nullptr)
            return head;
        ListNode *pre = head;
        ListNode *cur = head->next;
        ListNode *next;
        while (cur != nullptr) {
            next = cur->next;
            if (cur->val == pre->val) {
                pre->next = cur->next;
                delete cur;
            } else {
                pre = cur;
            }
            cur = next;
        }
        return head;
    }
};

1.4 LeetCode 86. 分隔链表

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

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

示例:

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

解法一：

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *dummy1 = new ListNode(-1);
        ListNode *dummy2 = new ListNode(-1);
        ListNode *tail1 = dummy1;
        ListNode *tail2 = dummy2;
        ListNode *cur = head;
        while (cur != nullptr) {
            if (cur->val < x) {
                tail1->next = cur;
                tail1 = tail1->next;
            } else {
                tail2->next = cur;
                tail2 = tail2->next;
            }
            cur = cur->next;
        }
        tail1->next = dummy2->next;
        tail2->next = nullptr;//断开tail2之后的节点，必须有
        return dummy1->next;
    }
};

1.5 LeetCode 328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

解法一：

class Solution {
public:
    ListNode *oddEvenList(ListNode *head) {
        ListNode *dummy1 = new ListNode(-1);
        ListNode *dummy2 = new ListNode(-1);
        ListNode *tail1 = dummy1;
        ListNode *tail2 = dummy2;
        ListNode *cur = head;
        int count = 1;
        while (cur != nullptr) {
            if (count % 2 == 1) {
                tail1->next = cur;
                tail1 = tail1->next;
            } else {
                tail2->next = cur;
                tail2 = tail2->next;
            }
            cur = cur->next;
            count++;
        }
        tail1->next = dummy2->next;
        tail2->next = nullptr;//断开tail2之后的节点，必须有
        return dummy1->next;
    }
};

1.6 LeetCode 2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法一：

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        ListNode *cur1 = l1;
        ListNode *cur2 = l2;
        int carry = 0;
        while (cur1 != nullptr || cur2 != nullptr) {
            int val1 = cur1 == nullptr ? 0 : cur1->val;
            int val2 = cur2 == nullptr ? 0 : cur2->val;
            cur->next = new ListNode((val1 + val2 + carry) % 10);
            carry = (val1 + val2 + carry) / 10;
            cur = cur->next;
            if (cur1 != nullptr)
                cur1 = cur1->next;
            if (cur2 != nullptr)
                cur2 = cur2->next;
        }
        if (carry != 0)
            cur->next = new ListNode(carry);
        return dummy->next;
    }
};

1.7 LeetCode 445. 两数相加 II

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

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

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

示例：

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

解法一：弹栈

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        stack<ListNode *> s1;
        stack<ListNode *> s2;
        ListNode *cur1 = l1;
        ListNode *cur2 = l2;
        while (cur1 != nullptr) {
            s1.push(cur1);
            cur1 = cur1->next;
        }
        while (cur2 != nullptr) {
            s2.push(cur2);
            cur2 = cur2->next;
        }

        ListNode *dummy = new ListNode(-1);
        int carry = 0;
        while (!s1.empty() || !s2.empty()) {
            /* int val1 = 0;
             if (!s1.empty()) {
                 val1 = s1.top()->val;
                 s1.pop();
             }
             int val2 = 0;
             if (!s2.empty()) {
                 val2 = s2.top()->val;
                 s2.pop();
             }*/
            int val1 = s1.empty() ? 0 : s1.top()->val;
            int val2 = s2.empty() ? 0 : s2.top()->val;
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            ListNode *tmp = new ListNode((val1 + val2 + carry) % 10);
            tmp->next = dummy->next;
            dummy->next = tmp;
            carry = (val1 + val2 + carry) / 10;
        }
        if (carry != 0) {
            ListNode *tmp = new ListNode(carry);
            tmp->next = dummy->next;
            dummy->next = tmp;
        }
        return dummy->next;
    }
};

第二部分虚拟头结点（dummy）

2.1 LeetCode 203. 移除链表元素

删除链表中等于给定值 *val* 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解法一：

class Solution {
public:
    ListNode *removeElements(ListNode *head, int val) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        ListNode *cur = head;
        while (cur != nullptr) {
            if (cur->val == val) {
                pre->next=cur->next;
                ListNode *delNode=cur;
                cur=cur->next;
                delete delNode;
            } else{
                pre=cur;
                cur=cur->next;
            }
        }
        ListNode *ans=dummy->next;
        delete dummy;
        return ans;
    }
};

解法二：

class Solution {
public:
    ListNode *removeElements(ListNode *head, int val) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        while (pre->next != nullptr) {
            if (pre->next->val == val) {
                ListNode *delNode=pre->next;
                pre->next=pre->next->next;
                delete delNode;
            } else{
                pre=pre->next;
            }
        }
        ListNode *ans=dummy->next;
        delete dummy;
        return ans;
    }
};

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

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

示例 1:

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

示例 2:

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

解法一：

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        ListNode *cur = dummy->next;
        while (pre->next != nullptr) { //终止条件
            //两种条件，同一种逻辑
            if (cur->next == nullptr || 
                	(cur->next != nullptr && cur->val != cur->next->val)) {
                pre = cur;
                cur = cur->next;
            } else {
                //while循环，一个一个删除节点
                while (cur->next != nullptr && cur->val == cur->next->val) {
                    ListNode *delNode=cur;
                    cur = cur->next;
                    pre->next = cur;
                    delete delNode;
                }
                ListNode *delNode=cur;
                cur = cur->next;
                pre->next = cur;
                delete delNode;
            }
        }
        return dummy->next;
    }
};

2.3 LeetCode 21. 合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解法一：迭代

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 == nullptr ? l2 : l1;
        return dummy->next;
    }
};

解法二：递归

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PfbBENwI-1605350637486)(C:\Users\Dong\AppData\Roaming\Typora\typora-user-images\image-20200922095101132.png)]

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

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

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

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

示例:

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-faR3d43m-1605350637489)(C:\Users\Dong\AppData\Roaming\Typora\typora-user-images\image-20200922102319411.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L86hSNFA-1605350637491)(C:\Users\Dong\AppData\Roaming\Typora\typora-user-images\image-20200922102553986.png)]

解法一：迭代

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy;
        while (pre->next != nullptr && pre->next->next != nullptr) {
            ListNode *node1 = pre->next;
            ListNode *node2 = pre->next->next;
            ListNode *next = node2->next;
            pre->next = node2;
            node2->next = node1;
            node1->next = next;
            pre = node1;
        }
        return dummy->next;
    }
};

解法二：递归

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

2.5 LeetCode *25. K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

方法一：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ov9Ey6X4-1605350637498)(C:\Users\Dong\AppData\Roaming\Typora\typora-user-images\image-20200922184158528.png)]

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *curTail = dummy;
        ListNode *top = head;
        ListNode *tail = dummy;
        while (true) {
            for (int i = 0; i < k; i++) {
                if (tail->next == nullptr) {
                    curTail->next = top;
                    return dummy->next;
                }
                tail = tail->next;
            }
            head = tail->next;
            tail->next = nullptr;
            curTail->next = reverse(top);
            curTail = top;
            tail = new ListNode(-1);//tail为新排序链表的头结点
            tail->next = head;
            top = head;
        }
    }
private:
    ListNode *reverse(ListNode *head) {
        if (head->next == nullptr) {
            return head;
        }
        ListNode *ans = reverse(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }
};

2.6 LeetCode 147. 对链表进行插入排序

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 1：

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

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解法一：（能通过，但很烂）

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = head->next;
        ListNode *top = cur->next;
        head->next = nullptr;
        cur->next = nullptr;
        do {
            head = dummy;
            while (head->next != nullptr) {
                if (cur->val <= head->next->val) {
                    cur->next = head->next;
                    head->next = cur;
                    break;
                }
                head = head->next;
                if (head->next == nullptr) {
                    head->next = cur;
                    break;
                }
            }
            cur = top;
            if (cur == nullptr)
                break;
            top = top->next;
            cur->next = nullptr;
        } while (true);
        return dummy->next;
    }
};

2.7 LeetCode 148*. 排序链表

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

示例 1:

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

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解析：

解法一：top down(自上向下递归)

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *fast = head->next;
        ListNode *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = nullptr;
        return merge(sortList(head), sortList(mid));
    }
private:
    ListNode *merge(ListNode *l1, ListNode *l2) {
        ListNode dummy(-1);//不是指针
        ListNode *cur = &dummy;//指针类型接收引用，不用释放内存
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val > l2->val)
                swap(l1, l2);
            cur->next = l1;
            l1 = l1->next;
            cur = cur->next;
        }
        if (l1 == nullptr) cur->next = l2;
        if (l2 == nullptr) cur->next = l1;
        return dummy.next;
    }
};

注：

时间复杂度O(nlogn)，空间复杂度O(logn)。时间复杂度满足题目要求，但空间复杂度不是常量，不满足要

求。但在LeetCode上可以提交。
ListNode dummy(-1);//不是指针

*ListNode cur = &dummy;

指针类型接收引用，不用释放内存。
merge([2,4,1],[2])，merge([2,4,1],[]) 都可以

merge递归方法

ListNode *merge(ListNode *l1, ListNode *l2) {
    if (l1 == nullptr) {
        return l2;
    } else if (l2 == nullptr) {
        return l1;
    } else if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

merge迭代方法

ListNode *merge(ListNode *l1, ListNode *l2) {
    ListNode dummy(-1);
    ListNode *cur = &dummy;
    ListNode *cur1 = l1;
    ListNode *cur2 = l2;
    while (cur1 != nullptr && cur2 != nullptr) {
        if (cur1->val < cur2->val) {
            cur->next = cur1;
            cur1 = cur1->next;
        } else {
            cur->next = cur2;
            cur2 = cur2->next;
        }
        cur = cur->next;
    }
    cur->next = cur1 == nullptr ? cur2 : cur1;
    return dummy.next;
}

数组递归排序

class Solution {
public:
    void mergeSort(int arr[], int low, int high) {
        if (low >= high) return;  // 终止递归的条件，子序列长度为1
        int mid = low + (high - low) / 2;  // 取得序列中间的元素
        mergeSort(arr, low, mid);  // 对左半边递归
        mergeSort(arr, mid + 1, high);  // 对右半边递归
        merge(arr, low, mid, high);  // 合并
    }

private:
    void merge(int arr[], int low, int mid, int high) {
        //low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
        int i = low, j = mid + 1, k = 0;  //mid+1为第2有序区第1个元素，j指向第1个元素
        int *temp = new int[high - low + 1]; //temp数组暂存合并的有序序列
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) //较小的先存入temp中
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        while (i <= mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
            temp[k++] = arr[i++];
        while (j <= high)//同上
            temp[k++] = arr[j++];
        for (i = low, k = 0; i <= high; i++, k++)//将排好序的存回arr中low到high这区间
            arr[i] = temp[k];
        delete[]temp;//释放内存，由于指向的是数组，必须用delete []
    }
};

解法二：top down(自上向下递归)

以后再做，嘻嘻~~~~

2.8 LeetCode 237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

Code：

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        ListNode *p=node->next;
        node->next=node->next->next;
        delete p;
    }
};

总结一下

这道题没有给出链表的头节点，而是直接给出要删除的节点，让我们进行原地删除。我们对于该节点的前一

个节点一无所知，所以无法直接执行删除操作。因此，我们将要删除节点的 next 节点的值赋值给要删除的节

点，转而去删除 next 节点，从而达成目的

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

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

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

Code1:

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *first = dummy;
        ListNode *second = dummy;
        for (int i = 0; i < n; ++i)
            first = first->next;
        while (first->next != nullptr) {
            first = first->next;
            second = second->next;
        }
        ListNode *p = second->next;
        second->next = second->next->next;
        delete p;
        return dummy->next;
    }
};

Code2：

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode *first = &dummy;
        ListNode *second = &dummy;
        for (int i = 0; i < n; ++i)
            first = first->next;
        while (first->next != nullptr) {
            first = first->next;
            second = second->next;
        }
        ListNode *p = second->next;
        second->next = second->next->next;
        delete p;
        return dummy.next;
    }
};

2.10 LeetCode 61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 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

Code：

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (head == nullptr) return head;
        ListNode *cur = head;
        int length = 1;
        while (cur->next) {
            length++;
            cur = cur->next;
        }
        int count = k % length;
        ListNode *first = head;
        ListNode *second=head;

        for (int i = 0; i < count; ++i)
            first = first->next;

        while (first->next != nullptr) {
            first = first->next;
            second = second->next;
        }

        first->next = head;
        head = second->next;
        second->next = nullptr;
        return head;
    }
};

2.11 LeetCode 143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路：寻找链表中点 + 链表逆序 + 合并链表

Code：

class Solution {
public:
    void reorderList(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return;
        ListNode *fast = head;
        ListNode *slow = head;
        // 寻找链表中点slow
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *l1 = head;
        ListNode *l2 = slow->next;
        slow->next = nullptr;
        // 链表逆序
        l2 = reverse(l2);
		// 合并链表
        ListNode dummy(-1);
        ListNode *cursor = &dummy;
        while (l2 != nullptr) {
            cursor->next = l1;
            l1 = l1->next;
            cursor = cursor->next;

            cursor->next = l2;
            l2 = l2->next;
            cursor = cursor->next;
        }
        cursor->next = l1;
        head = dummy.next;
    }
private:
    ListNode *reverse(ListNode *head) {
        if (head->next == nullptr)
            return head;
        ListNode *new_head = reverse(head->next);
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    }
};

2.12 LeetCode 234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

思路：

递归为我们提供了一种优雅的方式来方向遍历节点。

function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

Code：

class Solution {
    ListNode *frontPointer;
public:
    bool isPalindrome(ListNode *head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
private:
    bool recursivelyCheck(ListNode *head) {
        if (head == nullptr) return true;
        if(!recursivelyCheck(head->next))
            return false;
        if(head->val==frontPointer->val){
            frontPointer=frontPointer->next;
            return true;
        }
        return false;
    }
};

de *reverse(ListNode *head) {
if (head->next == nullptr)
return head;
ListNode *new_head = reverse(head->next);
head->next->next = head;
head->next = nullptr;
return new_head;
}
};


### 2.12 LeetCode [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)

请判断一个链表是否为回文链表。

**示例 1:**

输入: 1->2
输出: false


**示例 2:**

输入: 1->2->2->1
输出: true


**思路：**

递归为我们提供了一种优雅的方式来方向遍历节点。

```javascript
function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

Code：

class Solution {
    ListNode *frontPointer;
public:
    bool isPalindrome(ListNode *head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
private:
    bool recursivelyCheck(ListNode *head) {
        if (head == nullptr) return true;
        if(!recursivelyCheck(head->next))
            return false;
        if(head->val==frontPointer->val){
            frontPointer=frontPointer->next;
            return true;
        }
        return false;
    }
};

2020年第十一届蓝桥杯大赛软件类决赛(国赛) C/C++ 大学A组【题面】-爱代码爱编程

2020-11-14 标签: 算法 c++ 蓝桥杯分类: 国赛 # acm-区域赛/网络题面

记录一下国赛的题面，真的和省赛完全不是一个难度的。这次估计国三都混不到，还是太菜了QAQ，之后如果能补题解就补吧。题面的pdf文件我也上传到CSDN下载区了，内容和本篇文章相同。（题面真长，我复制到markdown修改格式都搞了半天） 11.15中午更新：混到个国三，然而并没什么用文章目录试题 A: 合数个数（5 分）试题 B: 含 2 天

2020第十一届蓝桥杯国赛C/C++B组总结-爱代码爱编程

2020-11-14 标签: 深度搜索算法队列分类: 参赛心得

2020/11/14裂开了第十一届蓝桥杯国赛C/C++B组总结主要是对填空进行总结（大题根本就不会），填空感觉做的还行？希望能拿到好成绩。答案不一定正确，主要是看该答案的人比较多，欢迎讨论。代码也是回来现敲的，欢迎指错。试题 A: 美丽的 2 本题总分:5 分【问题描述】小蓝特别喜欢 2,今年是公元 2020 年,他特别高兴。他

[剑指offer] 二维数组查找-爱代码爱编程

2020-11-14 标签: 算法剑指Offer分类: 算法

1，题目在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。输入 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]] 输出 true 2

风格迁移综述-爱代码爱编程

2020-11-14 标签: 人工智能算法机器学习神经网络计算机视觉

风格迁移综述 0 引言1 基于图像迭代的风格迁移方法1.1 基于最大均值差异的风格迁移1.2 基于马尔科夫随机场的风格迁移1.3 基于深度图像类比的风格迁移2 基于模型迭代的风格迁移算法2.1 基于生成模型的风格迁移2.2 基于图像重构解码器的风格迁移3 应用举例4 未来研究方向5 参考文献推荐论文：Y. Jing, Y. Yang, Z.

Dijkstra算法有关贪心与DP思想方面的思考-爱代码爱编程

2020-11-14 标签: 算法动态规划贪心算法 dijkstra分类: 算法

关于Dijkstra算法的讲解请参考这位大佬的博客：https://blog.csdn.net/heroacool/article/details/51014824 起算法老师布置了一个作业：Dijkstra算法是求解有向图最短路径的一个经典算法，也是应用贪心法的一个成功实例，请描述Dijkstra算法的贪心策略和具体算法。说实话，我一开始并未当作

C语言数据结构与算法--两数相加-爱代码爱编程

2020-11-14 标签: 算法分类: 数据结构与算法

/*server.c*/ #include <stdio.h> #include <stdlib.h> #include <string.h> // Definition for singly-linked list. struct ListNode { int val; struct ListNode

2020年第十一届蓝桥杯大赛软件类决赛(国赛) C/C++ 大学A组【题面】-爱代码爱编程

2020-11-14 标签: 算法 c++ 蓝桥杯分类: 国赛 # acm-区域赛/网络题面

记录一下国赛的题面，真的和省赛完全不是一个难度的。这次估计国三都混不到，还是太菜了QAQ，之后如果能补题解就补吧。题面的pdf文件我也上传到CSDN下载区了，内容和本篇文章相同。（题面真长，我复制到markdown修改格式都搞了半天） 11.15中午更新：混到个国三，然而并没什么用文章目录试题 A: 合数个数（5 分）试题 B: 含 2 天

C语言程序设计-多项式的合并运算-爱代码爱编程

2020-11-16 标签: c++ C 多项式多项式合并分类: 课程设计计算机软件课程设计汇总

课程设计题目及要求:多项式的合并运算【问题描述】设计一个实现任意长的多项式进行加减法运算的演示程序。【基本要求】使用链表结构实现。【测试数据】 7X500+9X100+2X3+2X2+100 与 3x3000+35X2000+18X100-2x3+1000 输出合并的结果：3x3000+35X2000 +7X^500 +27X^100+1100

std::find的使用-爱代码爱编程

2020-11-14 标签: c++ STL分类: 技术贴 c++ 代码

std::find可用于查找容器中是否存在某个特定值，对于基本类型的容器用法 int searchValue = 42; vector<int>::const_iterator result= find(vec.begin(), vec.end(), searchValue); if(result == vec.end()) {

Android-NDK-04-C++基础，面向对象编程 (类的定义与使用、单例的练习、运算符重载、继承、模板编程)-爱代码爱编程

2020-11-14 标签: Java c++ android分类: ndk

类的定义与使用： Student.h #ifndef NDK04_CODE_STUDENT_H #define NDK04_CODE_STUDENT_H #endif //NDK04_CODE_STUDENT_H #pragma once // 是在预处理器只保证引入一次，但是可能很多的编译器不支持，所以就需要以下的这种写法 #include

获取window系统一个目录下所有的文件名（除目录）-爱代码爱编程

2020-11-14 标签: c++

最近项目中优化一些代码等，给予项目中的代码进行重构，印象比较深的是对于文件操作来说，这些基本的小功能，在项目中经常遇到，如：最简单的获取window系统下某个目录下的所有文件名，为了完成这个功能，在window系统下需要添加头文件：#include <windows.h>，实现的代码如下： #include<iostream> #

PTA-梅森数-爱代码爱编程

2020-11-14 标签: c++

形如2^n −1的素数称为梅森数（Mersenne Number）。例如2^2 −1=3、2^3 −1=7都是梅森数。1722年，双目失明的瑞士数学大师欧拉证明了2^31−1=2147483647是一个素数，堪称当时世界上“已知最大素数”的一个记录。本题要求编写程序，对任一正整数n（n<20），输出所有不超过2^n−1的梅

3、链表-爱代码爱编程

链表

第一部分

1.1 LeetCode 206. 反转链表

1.2 LeetCode *92. 反转链表 II

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

1.4 LeetCode 86. 分隔链表

1.5 LeetCode 328. 奇偶链表

1.6 LeetCode 2. 两数相加

1.7 LeetCode 445. 两数相加 II

第二部分 虚拟头结点（dummy）

2.1 LeetCode 203. 移除链表元素

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

2.3 LeetCode 21. 合并两个有序链表

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

2.5 LeetCode *25. K 个一组翻转链表

2.6 LeetCode 147. 对链表进行插入排序

2.7 LeetCode 148*. 排序链表

2.8 LeetCode 237. 删除链表中的节点

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

2.10 LeetCode 61. 旋转链表

2.11 LeetCode 143. 重排链表

2.12 LeetCode 234. 回文链表

第二部分虚拟头结点（dummy）