day0702链表

JZ6 从尾到头打印链表

我的解法

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list  = new ArrayList();
       while( listNode!=null){
           list.add(listNode.val);
           listNode = listNode.next;
       }
        // 感觉此时的 ListNode.next != null 也不是很有必要;
        while(listNode !=null && listNode.next!=null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> listReverse = new ArrayList();
        while(list.listIterator().hasPrevious()){
            listReverse.add(list.listIterator().previous());
        }
           // listReverse.toArray();
        return listReverse;
    }
}

难点: 自己 不知道 util 下有哪些工具类, 工具类的方法名字也不记得 总体思路清晰:
1.根据 head 去遍历所有,放入一个容器里,

1. 遍历使用.next更新 head, 往容器里存入的是什么,是 节点类实例?还是节点类的值域;
2. 倒序遍历使用了 ListIterator及 previous ,根据 2 确定
3. 是否需要转换为java数组;

困惑点:

1. 题目写的输入 是 {1,2,3}, 这肯定不是一个 head, 而是一个容器对象实例;
2. 题目写的输出是[1,2,3] , 那么提示的 printListFromTailToHead 的返回值为什么不是 数组呀? 而是一个容器!
3. 还是说, 输入输出是测试用例?我不太懂

网友答案

// 更加容易理解一些;
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    ArrayList<Integer>  list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
                if(listNode  != null) {
                    printListFromTailToHead(listNode.next);
                    list.add(listNode.val); //  add最后一个, 倒数第二个;...正数第一个;
                }
        return list;
    }
}

import java.util.Collections;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        printListFromTailToHeadCore(ans,listNode);
        return ans;
    }
    private void printListFromTailToHeadCore(ArrayList<Integer> ans, ListNode listNode) {
        if (listNode == null){
            return;
        }
        printListFromTailToHeadCore(ans,listNode.next);
        ans.add(listNode.val);
    }
}

/**
*1.递归
*2.借用栈
*3.头插法，每个元素都往前插入
add(index,value)用法 小心些;
https://blog.csdn.net/qq_27093465/article/details/55211722
**/
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        while(listNode != null){
            array.add(0,listNode.val);
            listNode = listNode.next;
        }
        return array;
    }
}
// ?    
//         ArrayList<Integer> list = new ArrayList<>();
//          while(listNode != null){
//             list.add(listNode.val);
//             listNode = listNode.next;
//             }
//         int i = 0;
//         int j = list.size() - 1;
//         while(i < j){
//             int tmp = list.get(i);
//             list.set(i,list.get(j));
//             list.set(j,tmp);
//             i++;
//             j--;
//         }
//         return list;
// 借用栈
//         ArrayList<Integer> list = new ArrayList<>();
//         Stack <Integer> stack = new Stack<>();
//         if(listNode == null){
//             return list;
//         }
//         while(listNode != null){
//             stack.push(listNode.val);
//             listNode = listNode.next;
//         }
//         while(!stack.empty()){
//             list.add(stack.pop());
//         }
//         return list;

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.*;
public class Solution {
    /*
    // 方法一：先进后出，我们可以想到栈
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //用来存储链表中节点的值。
        Stack<Integer> reverse = new Stack<>();
        while(listNode != null){
            reverse.push(listNode.val);
            listNode = listNode.next;
        }
        //创建的题目要求的数据类型来存储反向的节点值。
        ArrayList<Integer> result = new ArrayList<>(); 
        while(!reverse.isEmpty()){
            //将值从栈中弹出，并添加到ArrayList中
            result.add(reverse.pop());
        }
        return result;
    }
    */
    /* 
    //方法一：递归
    ArrayList<Integer> arr = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            printListFromTailToHead(listNode.next);
            arr.add(listNode.val);
        }
        return arr;
    }
    */
    /*
    // 方法二：使用ArrayList 中有个方法是 add(index,value)
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = listNode;
        while(tmp!=null){
            list.add(0,tmp.val);
            tmp = tmp.next;
        }
        return list;
    }
    */
    // 链表反转法
    // 时间复杂度: O(n)
    // 空间复杂度: O(n)
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> vals = new ArrayList<>();
        ListNode pre = null, cur = listNode, next;
        // 反转链表
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 添加到vals中
        cur = pre;
        while (cur != null) {
            vals.add(cur.val);
            System.out.println(cur.val);
            cur = cur.next;
        }
        return vals;
    }
}

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode l=listNode;
        ArrayList<Integer> arrayList=new ArrayList<>();
        if(listNode==null) return arrayList;
        Stack<Integer> stack=new Stack<>();
    // 先进入 在后面;
        while(l.next!=null){
            stack.push(l.val);
            l=l.next;
        }
        stack.push(l.val);
        while (!stack.empty()){
            arrayList.add(stack.pop());
        }
        return  arrayList;
    }
  public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 建立一个list
            ArrayList<Integer>  list  = new ArrayList();
            Stack<Integer>  stack = new Stack();
        // 先入栈, 是元素的值
        while(listNode != null){
            stack.push(listNode.val); 
            listNode = listNode.next;
        }
        // 出栈并加入list
            while(!stack.isEmpty()){
                list.add(stack.pop());
            }
        return list;
    }

JZ24 反转链表

我的答案

尽管描述的测试用例让人误会,还是根据代码区提示即可

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        if (head.next == null) return head;
          ListNode cur = head;
          ListNode pre = null;
     //
        while(cur!=null){
           ListNode temp = cur.next;
            cur.next = pre;// 在更改引用之前, 存储后一个节点
            pre = cur ; // 事先存储当前要调转节点的前一个节点;
            cur = temp;
        }
        return pre;
    }
}

其他

1. 栈

import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        // 无需使用if进行 head == null判断；
        while(head !=null){
            stack.push(head);
            head = head.next;
        }
        // 先推，后查; 做边界条件控制
        if(stack.isEmpty()){
            return null ;
        }
        ListNode node  = stack.pop();
        ListNode reverse = node;// 栈顶就是新链表的head；
        // 弹出一个后，有可能为空
        while(!stack.isEmpty()){
            ListNode  tempNode =     stack.pop();
            node.next = tempNode;
            // 写node.next更加符合  都是链表的序列元素；
            node = node.next // 我这里写的是tempNode;
            }
        node.next = null;
        return  reverse;
    }
}

  public ListNode ReverseList(ListNode head) {
        if(head != null) return head;
        // 新链表头节点
            ListNode newHead = null ;
        while(head != null){
            //   原链表 当前的下一个节点
            ListNode tempNode = head.next;
            // 这也是双向链表的实现方式;
            //  就是把 新的链表（头为newHead） 挂载到当前（head）的next（后面）即可；
            head.next = newHead;
            newHead = head;
            head = tempNode;
        }
            return newHead;
    }

:::info public ListNode reverseList(参数0) {
if (终止条件)
return;

逻辑处理（可能有，也可能没有，具体问题具体分析）
//递归调用<br />    ListNode reverse = reverseList(参数1);
逻辑处理（可能有，也可能没有，具体问题具体分析）<br />}

:::

 public ListNode ReverseList(ListNode head) {
        // 退出条件
       if(head == null || head.next == null){
            return head;
       }
        // 逻辑处理
        ListNode next = head.next;
        //从当前节点的下一个节点开始递归调用
       ListNode reverse =  ReverseList(next);
        //  reverse是反转之后的链表的头节点, 
        // 反转完之后, next是 链表的尾结点; 
        // 将当前节点head, 挂载到 next之后即可.
        next.next = head; // next 是当前节点的环.
        head.next = null ;  // 不这么做, 就会构成环.
        return  reverse;
    }

public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode reverse = ReverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reverse;
}
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ans
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。
时间复杂度：O(N)，其中 N 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度：O(N)，其中 N 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 N 层

合并排序链表

:::info 当两个链表为空时，返回空链表
当两个链表均不为空，谁的当前元素小，将谁放入新的链表中，然后指针右移
当最后只有一个非空链表时，直接放在新链表的右侧 :::

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
         if(list1 == null && list2 == null){
             return null;
         }
        //其他情况,则
        // 定义一个新的ListNode;
        ListNode  myList = new ListNode(0); //  即将被返回的 头结点
        ListNode now = myList;
        while(list1 !=null && list2 !=null){
            int key; // 临时存储区
            if( list1.val <= list2.val){
                key = list1.val;
                list1 = list1.next;
            }else{
                    key = list2.val;
                list2 = list2.next;
            }
            // 把较小的值封装起来, 准备给到新的链表;
            ListNode  node = new ListNode(key);
            now.next = node;
            now = now.next;
    }
        // 只要List1 和List2 有一个为null;
        if(list1 != null ) now.next = list1;
        if(list2 != null) now.next = list2;
        return myList.next; // myList是一个无用的领头;
}

链表公共节点

1. 快慢指针

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while(l1 != l2){
            // 同样长度,同样速度;那么 只要有相交,就一定会遇到.
                l1 = (l1 ==null)?pHead2:l1.next;
            l2 = (l2==null)?pHead1:l2.next;  // 当l2 ==null时, 转向pHead1;
        }
        // 若l1 == l2 == null; 也算是一种相遇把.
        return l1;// return l2; 
    }
}

时间复杂度：O(m+n)。链表1和链表2的长度之和。
空间复杂度：O(1)。常数的空间。

1. 集合set

先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可

 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
      HashSet<ListNode> set =  new HashSet<ListNode>();
        // 将List1 全部加入set里;
        while(pHead1!=null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2 != null){
            // 若set里面含有pHead2
        // 必定是第一个公共节点
            if(set.contains(pHead2)){
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        // 若集合set不包含链表2的任意一个节点, 说明节点, 直接返回null;
        return null;
    }

时间复杂度O(M+N)：M, N分别表示 pHead1， pHead2的链表长度，最差情况下需要遍历完两个链表
空间复杂度O(M)：需要额外集合空间存储 pHead1 结点

1. 统计两个链表的长度

在仅仅遍历一次的情况下, 多余的长度的那部分, 是不可能成为公共区域的节点的.

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
             int lenA =length(pHead1);
        int lenB  = length(pHead2);
        while(lenA != lenB){
            if(lenA>lenB){
                pHead1 = pHead1.next;
                lenA--;
            }else{
                pHead2 = pHead2.next;
                lenB--;
            }
        }
        // 必定lenA == lenB;
        while(pHead1 != pHead2){// 引用类型; 指向同一个节点(对象)
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        // 一定相等了 pHead1 == pHead2 ; 
        //1. 都为null
        // 2. 公共节点
        return pHead1;
    }
    private int length(ListNode node){
        int length = 0 ;
        //不可使用ｉｔｅｒａｔｏｒ，那是容器的迭代器；　当前是一个容器里面的节点；
        while(node != null){
            node = node.next; 
            length++; 
        }
        return length;
    }
}

1. 链表公共部分

链表中环的入口节点

HashSet

首先这题要我们找链表的环入口结点，最常规易懂的解法就是遍历整个链表结点，然后用哈希表来存储已访问过的结点，最后进行对比。 若该结点已存在哈希表中，则代表该结点是我们要找的环形链表的入口结点；否则把结点添加到哈希表中，继续往下遍历。

 public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashSet<ListNode>  set = new HashSet<ListNode>();
        while(pHead != null){
                // 一定要先判断pHead是否已经被set包含了;
             if(set.contains(pHead)){
                return pHead;
            }
            // pHead必定是不重复的.
            set.add(pHead);
            pHead = pHead.next;
        }
    }
时间复杂度：O(n)，需要将链表的所有结点遍历一遍，时间复杂度为O(n)；
空间复杂度：O(n)，需要额外的n空间的hashset来存储结点。

快慢指针

        public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead ==null){
            return pHead;
        }
            ListNode slow = pHead;
            ListNode fast = pHead;
            while( fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                // 记录下 快慢指针 第一次相遇的节点
                if(slow == fast) break;
            }
            // 快指针指向null,则无环
            if(fast == null  || fast.next == null){
                return null;
            }
            fast = pHead; // 将快指针拎回头
            while( fast != slow){
                fast = fast.next;
                slow = slow.next; // 起点 和 第一次相遇的节点 以相同速度出发, 相遇即为入口
            }
            return fast;
            }
}
时间复杂度：O(n)，需要将链表的所有结点遍历一遍，时间复杂度为O(n)；
空间复杂度：O(1)，需要额外两个快慢指针来遍历结点。
时间复杂度：O(n) (其中n为链表中节点的数目,快慢指针走过的距离都不会超过链表的长度)
空间复杂度：O(1) (双指针使用常数大小的额外空间)

无环

有环

结论证明 :::info 1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。 :::

倒数第k个节点

快慢指针

:::info 起始先让快指针 fast 先走 步，此时 fast 和 slow 之间距离为 ，之后让 fast 和 slow 指针一起走（始终维持相对距离为 ），当 fast 到达链表尾部，slow 即停在倒数第 个节点处。 :::

public class Solution {
    /**
        快慢指针有 两倍速度, 有 先k步
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode fast  = pHead ; 
        ListNode slow = pHead; 
        int count =1 ;
        while(count <= k){
            // 快指针先走k步,若发现走着走着fast为null;说明k大于链表长度;
            if(fast == null){
                return null;
            }
            // if 判断必须放在最前面;
            count++;
            fast = fast.next;
        }
        // 双指针同时走
        while(fast != null){
            fast = fast.next;
            slow =slow.next;
        }
        return slow;
    }
}
时间复杂度：O(N)
空间复杂度: O(1)

反转链表+头插法

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
        快慢指针有 两倍速度, 有 先k步
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
       ListNode  newHead = null; 
        ListNode cur = pHead;
        int n = 0 ;
        while(cur != null){
            // 保存原链下一个
            ListNode  temp =  cur.next ; 
            // 反转指向
            cur.next = newHead;
            // 将新链表元素更新为当前原链表的节点
            newHead = cur ; 
            // 移动旧链表元素到 旧链表的下一个;
            cur = temp;
            // 遍历个数+1;
            n++;
        } // 跳出循环后, newHead将会是 新链表的头结点
        ListNode  kHead  = null ; 
        ListNode p = newHead; // 从头结点移动, 头插法
        int count = 1; 
        if(n < k){ // 无法等于
            // 链表长度不足, 就没有倒数第k个;
            return null;
        }
         while(count<=k){
             ListNode temp = p.next;
             p.next =  kHead;
             kHead = p;
             p = temp;
             count++;
         }   
        return kHead; //KHead是 头插法产生链表的头结点;
    }
}

堆栈

  public ListNode FindKthToTail (ListNode pHead, int k) {
  //    边界条件判断;
        if(pHead == null || k == 0 ){
            return null;
        }
        // 
        Stack<ListNode> stack = new Stack<>();
        while(pHead != null){
            stack.push(pHead);
            pHead = pHead.next;
        }
        // 观察栈的长度 是否小于k
        if(stack.size() < k){
            return null;
        }
        //弹栈
        ListNode  newHead = stack.pop();
        // 只要第k个元素;   因为在 while()之前 已经弹栈一次了.
        while(--k > 0 ){
            newHead  = stack.pop();
        }
        return newHead;
    }

删除链表中重复节点

迭代

public ListNode deleteDuplication(ListNode pHead) {
        ListNode dummy = new ListNode(-1); //新建一个虚拟节点, 其数据域不是很重要
        ListNode tail = dummy;
        while(pHead != null){
            // 进入循环迭代
                // 尾结点 或 不同值,才会添加到新的链表;
            if(pHead.next == null || pHead.next.val!=pHead.val){
                tail.next = pHead; 
                tail = pHead;
            }
            // 若出现 值相同,就持续移动到最后一位;
            while(pHead.next != null && pHead.val == pHead.next.val){
                pHead = pHead.next;
            }
            // 跳出连续相同的一段, 又向后移动了一位,  因为重复元素不保留;
            pHead = pHead.next; 
        }
        tail.next = null;
        return dummy.next; // dummu是虚假de,dummy.next才是第一个真的;
    }

递归

拓展

删除链表节点

我的代码

 public ListNode deleteNode (ListNode head, int val) {
        //  传入为空;
        if(head == null || head.next == null){
            return null;
        }
        ListNode newHead = head;
        // 迭代整个链表
        while(head != null){
            if(head.val == val){
                head.next  = head.next.next;
            }
        }
        return newHead;
    }

:::info public ListNode deleteDuplication(ListNode pHead) {
ListNode dummyNode = new ListNode(-1);
ListNode tail = dummyNode;
if(pHead == null){
return null;
}
while( pHead != null){
// 1. 当前与下一个节点值不等 ; pHead.next == null到达末尾, 不存在下一个节点了;
if( pHead.next == null || pHead.val != pHead.next.val ){
// 拼接到 虚拟节点尾部
tail.next = pHead;
// 更新tail
tail = pHead;
}
// 只要相等就一直处理;
while(pHead.next != null && pHead.val == pHead.next.val){

pHead = pHead.next;

// 没有事先保存好下一个节点的使用
// pHead = pHead.next;
// pHead.next = pHead;
}
pHead = pHead.next;
}
// 为了删除那个重复的唯一项

tail.next = null;
return dummyNode.next;



} :::

网友解法

  public ListNode deleteNode (ListNode head, int val) {
         if(head == null) return null;
        // 虚拟一个头结点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head; // 人为添加一个节点;
        ListNode pre = dummyHead ;
        while(head != null){
            // 当发现val相等
            if(head.val == val){
                break;
            }
            //更新双指针迭代;
            pre = head ; 
            head = head.next;
        }
        // 结束上述循环 ,1 . break, 2. head == null
        if(head == null) return dummyHead.next; // 未找到需要删除值;
        pre.next = head.next; // 跳过 值相等的那个节点;
        return dummyHead.next;// 
    }