leetcode刷题之链表

leetcode刷题之链表
next指向下一个节点的地址
链表中的节点:每一个节点通常最少有两个属性，一个表示该节点的值，可以用val来表示，另外一个就是指向下一个节点的指针，可以用next表示。

	function ListNode(val) {
      this.val = val;
      this.next = null;
    }

第一题
leetcode刷题之链表
思路：不给单链表，给的是单链表中要删除的节点node，这个node已经存在单链表中，即这个节点的前一个节点是未知的，但下一个节点是可以知道的，那么可以把下一个的值赋给这个node，然后删除下一个节点即可：即把node下一个节点的地址

var deleteNode = function(node) {
	    node.val = node.next.val;
	    node.next = node.next.next;
	};
	//创建节点
	function ListNode(val) {
      this.val = val;
      this.next = null;
    }
    var node1=new ListNode(1);
    var node2=new ListNode(2);
    var node3=new ListNode(3);
    var node4=new ListNode(4);
    var node5=new ListNode(5);
    node1.next=node2;
    node2.next=node3;
    node3.next=node4;
    node4.next=node5;
    deleteNode(node2);
    console.log(node1);//删掉了node2节点
    console.log(node2);
    console.log(node3);

打印结果：
leetcode刷题之链表
第二题

思路：这道题要用双指针来实现。先用first指针前进n，然后让second从head开始和first一起前进，直到first到了末尾，此时second的下一个节点就是要删除的节点。（另外，若first一开始前进n就已经不在链表中了，说明要删除的节点正是head节点，那么直接返回head的下一个节点接口。）

var removeNthFromEnd = function(head, n) {
	    let first=head,second=head;
	    while(n>0){
	        first=first.next;
	        n--;
	    }
	    if(!first) return head.next;//删除的是头节点
	    while(first.next){
	        first=first.next;
	        second=second.next;
	    }
	    second.next=second.next.next;
	    return head;
	};
   //创建节点
	function ListNode(val) {
      this.val = val;
      this.next = null;
    }
   var node1=new ListNode(1);
   var node2=new ListNode(2);
   var node3=new ListNode(3);
   var node4=new ListNode(4);
   var node5=new ListNode(5);
   node1.next = node2;
   node2.next = node3;
   node3.next = node4;
   node4.next = node5;
   console.log(removeNthFromEnd(node1,5))

删除了头节点
leetcode刷题之链表
第三题

思路：递归：将头节点和头节点后面的节点反转，头节点后面的节点则递归反转

var reverseList = function(head) {
    if (head == null || head.next == null) return head;
    var list = reverseList(head.next);
    var last = list;
    while (last.next != null) last = last.next;
    last.next = head;
    head.next = null;
    return list;
};

第四题
leetcode刷题之链表
思路：递归解决：若其中某条链表为空，那必然是返回另一条不为空的了。比较两条链表的头节点的大小，将较小者作为新链表的头节点，然后递归调用方法即可。

var mergeTwoLists = function(l1, l2) {
    	if(!l1) return l2;
    	if(!l2) return l1;
    	let head;
    	if (l1.val<l2.val) {
    		head=l1;
    		head.next=mergeTwoLists(l1.next,l2);
    	}else{
    		head=l2;
    		head.next=mergeTwoLists(l1,l2.next);
    	}
    	return head;
};

第四题
leetcode刷题之链表
思路：O(n)的时间复杂度意味着只能遍历一趟链表，O(1)的空间复杂度意味着只能使用常数个变量（也就是不能使用数组、集合等变量）。于是想到，设置两个字符串变量，一个保存正向的链表元素，一个保存反向的链表元素，遍历完判断是否相等即可。

var isPalindrome = function(head) {
    let str = '',             // 正向
      str_reverse = ''      // 反向
  while (head) {
    str += head.val;
    str_reverse = head.val + str_reverse;//将下一个放在前面
    head = head.next;
  }
  return str === str_reverse;
};

第五题
leetcode刷题之链表思路：设置两个指针p1，p2。p1每次走一步，p2每次走两步。
若没有环，则两者不会碰到，若有环，则必然会碰到。

var hasCycle = function(head) {
    if(!head||!head.next) return false;
    let p1=head,p2=head.next;
    while(p2&&p2.next){
        if(p1==p2) return true;
        p1=p1.next;
        p2=p2.next.next;     
    }
    return false;
};

leetcode刷题之链表

相关推荐