Skip to content

Latest commit

 

History

History
106 lines (83 loc) · 2.15 KB

反转链表.md

File metadata and controls

106 lines (83 loc) · 2.15 KB

请实现一个反转链表

示例:

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

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

你的答案:

迭代实现:

function reverseFunc(head){
    if (head === null || head.next === null){
        return head;
    }
    
    //pre->上一个节点,next->下一个节点,head->当前节点
    var pre = null;
    var next = null;
    while (head !== null) {
        next = head.next;//next = obj2,缓存下一个节点
        head.next = pre;//obj1.next = null-->这是关键代码,改变当前节点的下一个节点
        pre = head;//pre = obj1,缓存当前节点,将当前值作为上一个节点
        head = next;//head = obj2,更新当前节点
        
        /*迭代过程
        next = head.next;//next = obj3
        head.next = pre;//obj2.next = obj1
        pre = head;//pre = obj2
        head = next;//head = obj3
        
        next = head.next;//next = null
        head.next = pre;//obj3.next = obj2
        pre = head;//pre = obj3
        head = next;//head = null
        */        
    }
    return pre;  
}

/*******************************测试用例*******************************/
//构建链表
var obj3 = {
  name:'obj3',
  next:null
}
var obj2 = {
  name:'obj2',
  next:obj3
}
var obj1 = {
  name:'obj1',
  next:obj2
}


//输出链表
 function printLst(node){ 
  var p   = node;
  while(p){
      console.log(p.name)
      p = p.next;
  }
}

printLst(reverseFunc(obj1));//obj3,obj2,obj1

递归实现:

var reverseList = function(head) {
  if (head === null || head.next === null) {
    return head;
  }
  
  var new_head = reverseList(head.next);  // 反转后的头节点
  head.next.next = head;                  // 将反转后的链表的尾节点与当前节点相连
  head.next = null;
  return new_head;
};

/***************测试用例********************/
function listNode(val) {
     this.val = val;
     this.next = null;
}

let node3 = new listNode();
node3.val = 'node3';
node3.next = null;

let node2 = new listNode();
node2.val = 'node2';
node2.next = node3;

let node1 = new listNode();
node1.val = 'node1';
node1.next = node2;

console.log(reverseList(node1));