数组-链表-栈-队列（下）

LeetCode

66. 加一(模板题)

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

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

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

解题思路

1. 位数上加1有两种情况，9加1，和不是9加1
   不是9加1，return
   是9加1，进位，循环到上一位，重复判断
   
2. 如果循环走完了，说明都产生的进位，需要在最前面补1

完整代码

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(let i=digits.length-1;i>=0;i--){

        digits[i]++
        digits[i]=digits[i]%10

        if(digits[i]!==0){
            return digits
        }
    }

    // 走到这里，说明全部发生了进位
    // 前补1
    digits.unshift(1)

    return digits
};

25. K 个一组翻转链表

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

解题思路

1. k个一组翻转转换为单链表的翻转
2. 单链表翻转添加限制条件，走k步一个翻转
3. 每次翻转前，需要记录原来的头部（oldHead），翻转后的头部（newHead），以及原来链表k步后下一个节点的指针（temp）,pre指针（最初在保护节点，每次翻转变为翻转后的头部）
4. 翻转完成后  pre.next=翻转后的头部 pre=原来的头部(即翻转的尾部)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {

    // 解题思路

    // k个一组翻转链表

    // 转换为单链表翻转

    // 每k步翻转一次单链表


    // 单链表翻转
    const resloveList=(head,k)=>{
        if(!head){
            return null
        }

        let pre=null
        let p=head
        let step=0
        while(p!=null&&step<k){
            step++

            let temp=p.next

            p.next=pre

            pre=p

            p=temp

           
        }

        return pre

    }

    
    // k步一个翻转
    // 保护节点
    let secureNode=new ListNode(-1)
    secureNode.next=head
    // 保护节点

    let p=head
    let step=0
    // 原来链表的头部
    let oldHead=head
    let pre=secureNode

    // let old
    while(p){                                                                        
        p=p.next
        step++

        if(step===k){
            let temp=p
            // 翻转
            let newHead=resloveList(oldHead,k)
            step=0
            pre.next=newHead
            pre=oldHead

            oldHead=temp
            // console.log(oldHead,'oldHead')
            p=temp
        }     
    }

    pre.next=oldHead

    return secureNode.next

};