1.从尾到头打印链表值

输入一个链表的头节点从尾到头反过来返回每个节点的值(用数组返回)

思路

1如果使用数组来保存反转之后的链表数据这样只需要使用到队列或栈的知识关键是unshif和push,reverse函数

2如果不使用数组可以考虑使用双指针的办法来解决主要将头结点的next改为null,然后接下来的每个值都改一下next值

   //从尾到头打印链表值
    //数组法
    var resver = function (head) {
      let arr = [];
      while (head !== null) {
        arr.unshift(head);
        head = head.next;
      }
      return arr;
    };
    //双指针法
    var resver=function(head){
      let temp=null;//保存中间值而已
      let cut=head;//代表要改变他的next的值
      let pre=null;//代表cut要指向的next值
      while(cut!==null){//1!==null   2!==null
        temp=cut.next;//temp=1.next:2   temp=2.next:3
        cut.next=pre;//cut.next:1.next=null  cut.next:2.next=1
        pre=cut;//pre=1  pre=2
        cut=temp;//cut=2  cut=3
      }
      return pre;
    }

2.两两交换链表中的节点

 

给定一个链表两两交换其中相邻的节点并返回交换后的链表。

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

 

 //两两交换链表中的节点
    var head = [1, 2, 3, 4, 3];
    var resver = function (head) {
      if (head == null || head.next == null) return head;
      let pm = new LinkNode(0, head);
      // rm是指针pm是虚拟头结点
      let rm = pm;
      while (rm.next && rm.next.next) {
        //1 2,3 4,3.next=null退出循环
        // temp代表要交换的第一个数值
        let temp = rm.next; //temp=1  temp=3
        // cut代表要交换的第二个数值
        let cut = rm.next.next; //cut=2  cut=4
        //将两个数值交换的前一个数值的next改为第二个数值
        rm.next = cut; //rm.next=2   rm.next:1.next=4
        //将第一个数值的next改为第二个数值的下一个数值
        temp.next = cut.next; //temp.next:1.next=2.next:3    3.next=4.next:null
        // 将第二个数值的next改为第一个数值
        cut.next = temp; //cut.next:2.next=1   4.next=3
        // 这里的rm代表要交换的两个数值的前一个数值
        rm = temp; //rm=1 rm=3
      }
      return pm.next;
    };

3.删除链表的倒数第N个节点

给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。

思路

双指针的经典应用如果要删除倒数第n个节点让fast移动n步然后让fast和slow同时移动直到fast指向链表末尾。删掉slow所指向的节点就可以了。

 // 删除链表的倒数第n个结点
    var dele = function (head, n) {
      let rm = new LinkNode(0, head);
      let slow = rm;
      let fast = rm;
      while (n--) {
        fast = fast.next;
      }
      while (fast.next !== null) {
        slow = slow.next;
        fast = fast.next;
      }
      // 这里注意不要写成slow.next=fast;因为可能fast不止只有一个值
      slow.next = slow.next.next;
      return rm.next;
    };

 4.合并两个排序的链表

输入两个递增排序的链表合并这两个链表并使新链表中的节点仍然是递增排序的

//合并两个递增的链表
    var sortArr = function (arrA, arrB) {
      let lot = new LinkNode(0, arrA);
      let p1 = arrA;
      let p2 = arrB;
      let temp = lot;
      if (!p1) {
        return p2;
      }
      if (!p2) {
        return p1;
      }
      while (p1 && p2) {
        if (p1.val < p2.val) {
          temp.next = p1;
          p1 = p1.next;
        } else {
          temp.next = p2;
          p2 = p2.next;
        }
        temp = temp.next;
      }
      temp.next = p1 ? p1 : p2;

      return lot.next;
    };

5.链表相交

给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。

图示两个链表在节点 c1 开始相交

 

思路

先找到两个链表的长度len1len2 让长一点的链表先走len2-len1步使得两个链表距离链表尾部的长度相同 两个链表一起走并比较节点是否相同相同即为公共节点判断是否相同是需要值相同并下一个节点也相同

var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB){return null;}
    let len1 = getLength(headA);
    let len2 = getLength(headB);
    let long, short, gap;
    //判断哪个链表长度更长
    if(len1 > len2){
        long = headA;
        short = headB;
        gap = len1 - len2;// 求长度差
    }else{
        long = headB;
        short = headA;
        gap = len2 - len1;// 求长度差
    }
    //让长链表先走gap步
    while(gap-- > 0){
        long = long.next; // 让curA和curB在同一起点上末尾位置对齐
    }
    //两个链表一起走判断第一个公共节点
    while(long){
        if(long === short){// 遍历curA 和 curB遇到相同则直接返回
            return long;
        }
        long = long.next;
        short = short.next;
    }
    return null;
};
function getLength(head){
    let cur = head;
    let len = 0;
    while(cur){
        len++;
        cur = cur.next;
    }
    return len;
}

6.移除链表元素

可以设置一个虚拟头结点这样原链表的所有节点就都可以按照统一的方式进行移除了。

删除链表中等于给定值 val 的所有节点。

输入head = [1,2,6,3,4,5,6], val = 6 输出[1,2,3,4,5]

 //移除链表元素
    var dele=function(val,head){
      let headnode=new LinkNode(0,head);
let cut=headnode;
      while( cut.next){
      
        if( cut.next.val==val){
          cut.next=cut.next.next;

        }else{
          cut=cut.next;
        }
      }
      return headnode.next;
    }