/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function ReverseList(pHead)
{
// write code here
//递归终止条件
if(!pHead||!pHead.next) return pHead;
let newhead = ReverseList(pHead.next);
pHead.next.next = pHead;
pHead.next = null;
return newhead;
}
module.exports = {
ReverseList : ReverseList
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
function reverseBetween( head , m , n ) {
// write code here
//判断条件
if(!head || !head.next || m===n) return head;
//找到m前和n后的点start和end
let start=null,
end=null,
cur=head;
for(let i=1;i<=n;i++){
if(i===m-1){
start=cur;
}
cur=cur.next;
}
end=cur;
//节点反转
let pre=null,
next=null;
//当不是从头节点开始反转时
if(m>1){
cur=start.next;
while(cur!==end){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
start.next.next=end;
start.next=pre;
}else{
cur=head;
while(cur!=end){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
head.next=end;
head=pre;
}
return head;
}
module.exports = {
reverseBetween : reverseBetween
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
function reverseKGroup( head , k ) {
// write code here
let pre=null;
let current=head;
let node=head;
//判断这一组是否够k个 不够的话直接返回 保持原样
for(let i=0;i<k;i++){
if(node===null){
return head
}
node=node.next;
}
//反转
//出来的时候current指向下一组的第一个
for(let i=0;i<k;i++){
let next=current.next;
current.next=pre;
pre=current;
current= next;
}
// 经过反转后 head已经成为了最后一个节点
head.next=reverseKGroup(current,k)
return pre//返回这一组原本的最后一个节点(反转后这个节点已经是第一个节点了)
}
module.exports = {
reverseKGroup : reverseKGroup
};
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2)
{
// write code here
if(!pHead1) return pHead2;
if(!pHead2) return pHead1;
if(pHead1.val<=pHead2.val){
pHead1.next=Merge(pHead1.next,pHead2);
return pHead1;
}else{
pHead2.next=Merge(pHead2.next,pHead1);
return pHead2;
}
}
module.exports = {
Merge : Merge
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @return bool布尔型
*/
function hasCycle( head ) {
// write code here
while(head){
if(head.flag){
return true;
}
head.flag=true;
head=head.next;
}
return false;
}
module.exports = {
hasCycle : hasCycle
};
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
// write code here
//一直往后走 每走一步标记一次 碰到的第一个标记过的就是入口
while(pHead){
if(pHead.flag){
return pHead;
}else{
pHead.flag=true;
pHead=pHead.next;
}
}
}
module.exports = {
EntryNodeOfLoop : EntryNodeOfLoop
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
function FindKthToTail( pHead , k ) {
// write code here
if(!pHead||!pHead.next) return 0;
//快慢指针 先让快指针走k步
let slow=pHead,fast=pHead;
for(let i=0;i<k;i++){
if(!fast) return 0;
fast=fast.next;
}
//再让快慢指针一起走 当快指针到了最末尾 慢指针就到了倒数第k个
while(fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
module.exports = {
FindKthToTail : FindKthToTail
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
function removeNthFromEnd( head , n ) {
// write code here
//这个用快慢指针 先让快指针先走n步 然后慢指针与快指针一起走
//当快指针到了终点的时候 慢指针就到了倒数第n个
if(head===null) return null;
let fast=head,slow=head;
for(let i=0;i<n;i++){
fast=fast.next;
}
//如果fast指针此时为null说明这个n等于链表的长度
if(fast===null){
return head.next;
}
while(fast.next!==null){
fast=fast.next;
slow=slow.next;
}
//到这一行的时候slow是倒数第n个节点的前一个节点
slow.next=slow.next.next;
return head;
}
module.exports = {
removeNthFromEnd : removeNthFromEnd
};
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
if (pHead1 == null || pHead2 == null) return null;
let p1 = pHead1;
let p2 = pHead2;
while (p1 !== p2){
p1 = p1.next;
p2 = p2.next;
if (p1 === p2) break;
if (p1 === null) p1 = pHead2;
if (p2 === null) p2 = pHead1;
}
//这里在外面返回p1是考虑到如果p1 p2第一个节点就是公共的情况
return p1;
}
module.exports = {
FindFirstCommonNode : FindFirstCommonNode
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
function addInList( head1 , head2 ) {
// write code here
//把所有的节点取出来
let stack1=[],stack2=[];
let p1=head1,p2=head2;
while(p1){
stack1.push(p1);
p1=p1.next;
}
while(p2){
stack2.push(p2);
p2=p2.next;
}
let jinwei=0;//之前的进位
let pHead = new ListNode(-1);
let pre = pHead;
while(stack1.length||stack2.length){
let node1=stack1.pop();
let node2=stack2.pop();
let val1 = node1 ? node1.val : 0;
let val2 = node2 ? node2.val : 0;
let falseValue=val1+val2+jinwei;
let trueValue=falseValue%10;
//进位有可能是0或1
jinwei = (falseValue - trueValue) / 10;
let node = new ListNode(trueValue);
node.next=pre.next;
pre.next=node;
}
if(jinwei===1){
let node=new ListNode(1);
node.next=pHead.next;
pHead.next=node;
}
return pHead.next;
}
module.exports = {
addInList : addInList
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
function sortInList( head ) {
// write code here
let arr=[];
let p=head;
while(p){
arr.push(p.val)
p=p.next;
}
arr.sort((a,b)=>(a-b));//降序排序
let len=arr.length;
let node=new ListNode();
let newHead=node;
for(let i=0;i<len;i++){
node.next=new ListNode(arr[i]);
node=node.next;
}
return newHead.next
}
module.exports = {
sortInList : sortInList
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
function isPail( head ) {
// write code here
let arr=[],res=[];
while(head){
arr.push(head.val);
res.push(head.val);
head=head.next;
}
arr.reverse();
for(let i=0;i<arr.length;i++){
if(arr[i]!==res[i]) return false;
}
return true
}
module.exports = {
isPail : isPail
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
function oddEvenList( head ) {
// write code here
if(!head||!head.next) return head;
let arr=[],even=[],odd=[];//even是偶 odd是奇
while(head){
arr.push(head.val);
head=head.next;
}
for (let i=0;i<arr.length;i++){
if(i%2===0) even.push(arr[i]);
if(i%2===1) odd.push(arr[i]);
}
let newHead=new ListNode(null);
let node=newHead;
for(let i=0;i<even.length;i++){
node.next=new ListNode(even[i]);
node=node.next;
}
for(let i=0;i<odd.length;i++){
node.next=new ListNode(odd[i]);
node=node.next;
}
return newHead.next;
}
module.exports = {
oddEvenList : oddEvenList
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @return ListNode类
*/
function deleteDuplicates( head ) {
// write code here
if(!head||!head.next) return head;
let cur=head;
while(cur.next){
if(cur.val===cur.next.val){
cur.next=cur.next.next;
}else{
cur=cur.next;
}
}
return head;
}
module.exports = {
deleteDuplicates : deleteDuplicates
};
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @return ListNode类
*/
function deleteDuplicates( head ) {
// write code here
// write code here
if(head==null||head.next==null) return head;
let node=new ListNode(0);
node.next=head;
let pre=node,cur=head;
while(cur!=null&&cur.next!=null){
if(cur.val===cur.next.val){
let t=cur.next;
while(t!=null&&t.val==cur.val){
t=t.next;
}
pre.next=t;
cur=t;
}else{
pre=pre.next;
cur=cur.next;
}
}
return node.next;
}
module.exports = {
deleteDuplicates : deleteDuplicates
};