反转链表 (25)

[编程题]反转链表 (25)

热度指数：26480 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 146M，其他语言293M
算法知识视频讲解

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为
3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。

输入描述:

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10⁵)、以及正整数K(<=N)，即要求反转的
子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。

输出描述:

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

示例1

输入

00100 6 4<br/>00000 4 99999<br/>00100 1 12309<br/>68237 6 -1<br/>33218 3 00000<br/>99999 5 68237<br/>12309 2 33218

输出

00000 4 33218<br/>33218 3 12309<br/>12309 2 00100<br/>00100 1 99999<br/>99999 5 68237<br/>68237 6 -1

算法知识视频讲解

JavaScript

TS-------

JavaScript AC

用到了递归，我没有采用数组作为辅助空间，而是用了一个对象，存放这些结点，好在原地上进行修改
在牛客上测试该题代码，不仅要考虑了一个单链表的情况；
还要考虑当所给的节点中有不在所给开头的单链表中的节点时，应忽略其它节点；
还有，当K = 1, K > 有效节点时，不用反转，直接输出所给开头的单链表。

var arr = readline().split(' ');
var l = arr[0];
var num = arr[1];
var k = arr[2];
var node = {};
for(var i=0;i<num;i++){
    arr = readline().split(' ');
    address = arr[0];
    node[address] = {};
    node[address].data = arr[1];
    node[address].next = arr[2];
}
var nodeNum = 0;
countNode(l);
var count = nodeNum;
 
//反转
function reverse(p,k){
    var tail = p;
    var tmp = node[p].next;
    var previous;
    for(var i=1;i<k;i++){
        previous = tmp;
        tmp = node[previous].next;
        node[previous].next = p;
        p = previous;
    }
    count -= k;
    node[tail].next = count<k?tmp:reverse(tmp,k);
    return p;
}
//计数
function countNode(l){
    p = l;
    for(var i=0;i<num;i++){
        nodeNum++;
        if(node[node[p].next] != undefined){
            p = node[p].next;
        }else{
            break;
        }
    }
}
//打印
function myPrint(l){
    p = l;
    for(var i=0;i<nodeNum;i++){
        console.log(p,node[p].data,node[p].next);
        p = node[p].next;
    }
}
//输出
if(k>nodeNum||k===1){
    myPrint(l);
}else myPrint(reverse(l,k))

发表于 2019-11-29 17:39:56 回复(0)