LeetCode链表

//比较推荐的写法，简洁一点，在 lc 上提交区别不大
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyNode=new ListNode(-1);
    ListNode temp=dummyNode;
    dummyNode.next=temp;
    int carry=0;
    while(l1!=null || l2!=null){
        int sum= (l1!=null?l1.val:0) + (l2!=null?l2.val:0)+ carry;
        temp.next=new ListNode(sum%10);
        temp=temp.next;
        carry=sum/10;
        l1=l1!=null?l1.next:null;
        l2=l2!=null?l2.next:null;
    }
    if(carry!=0) temp.next=new ListNode(1);
    return dummyNode.next;
}

//这个解法有点偏了，为了不 new 节点直接在原链表上修改的
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=l1;
    int carry=0;
    ListNode last=l1;
    while(l1!=null && l2!=null){
        int sum= l1.val + l2.val+ carry;
        l1.val=sum%10;
        carry=sum/10;
        last=l1;
        l1=l1.next;
        l2=l2.next;
    }
    while(l1!=null && carry!=0){
        int sum = l1.val + carry;
        l1.val=sum%10;
        carry=sum/10;
        last=l1;
        l1=l1.next;
    }
    if(l2!=null){
        last.next=l2;
        while(l2!=null && carry!=0){
            int sum = l2.val + carry;
            l2.val=sum%10;
            carry=sum/10;
            last=l2;
            l2=l2.next;
        }
    }
    if(carry!=0) last.next=new ListNode(1);
    return dummyNode.next;
}

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    BigInteger b1 = new BigInteger(list2num(l1));
    BigInteger b2 = new BigInteger(list2num(l2));
    String resStr=b1.add(b2).toString();
    //再变成字符串存到连表里面
    ListNode res=new ListNode(1);
    ListNode real=res;
    for (int i=0;i<resStr.length();i++) {
        real.next=new ListNode(Integer.valueOf(resStr.charAt(i)-48));
        real=real.next;
    }
    return res.next;
}
public static String  list2num(ListNode l){
    String num="";
    while(l!=null){
        num=num+l.val;
        l=l.next;
    }
    return num;
}

public  ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //用数组的话不知道有多长，需要多遍历两遍
    Deque<Integer> stack1=new ArrayDeque<>();
    Deque<Integer> stack2=new ArrayDeque<>();
    ListNode res=new ListNode(-1);
    while(l1!=null){
        stack1.push(l1.val);
        l1=l1.next;
    }
    while(l2!=null){
        stack2.push(l2.val);
        l2=l2.next;
    }
    int carry=0;
    while(!stack1.isEmpty() || !stack2.isEmpty() || carry>0){
        int temp=(stack1.isEmpty()?0:stack1.pop())+(stack2.isEmpty()?0:stack2.pop())+carry;
        //头插法
        ListNode next=res.next;
        ListNode newNode=new ListNode(temp%10);
        res.next=newNode;
        newNode.next=next;
        carry=temp/10;
    }
    return res.next;
}

public static ListNode middleNode(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode fast=head;
        ListNode slow=head;
        // 1 2 3 4 5 6 7
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
}

//递归
public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    //从后往前
    head.next.next = head;
    head.next = null;
    return newHead;
}

//三指针迭代
public static ListNode reverseList2(ListNode head) {
    if(head==null)return head;
    ListNode pre=head;
    ListNode cur=head.next;
    ListNode temp;
    while(cur!=null){
        temp=cur.next;
        cur.next=pre;
        pre=cur;
        cur=temp;
    }
    head.next=null;
    return pre;
}

public static ListNode reverseBetween(ListNode head, int m, int n) {
    if(m==n) return head;
    //用来遍历
    ListNode pre=head;
    ListNode mid=head.next;
    ListNode rear=null;
    //在遍历的中间连接这个表 时间复杂厚度 O(N)
    //所以需要先保存 m 前的节点用于后面到 n 的时候连接 n 和前面的部分 preM
    //还要保存 m 节点，在后面遍历到 n 的时候将 M 节点和后面的部分连接
    //中间段的前后节点 
    ListNode preM =null;
    ListNode valM=head;
    //ListNode nNext=null;
    int count =1;
    while(count <=n-1){
        //count 的位置实际上是指的 pre 的位置因为只有 pre 是从 head 开始走的
        //尾指针后移
        rear=mid.next;
        if(count==m-1){
            //保存 M 点前面的节点和 M 节点
            preM=pre;
            valM=mid;
            //System.out.println("preM :"+preM.val);
        }
        if(count==n-1){
            //连接 n 后面节点的值
            valM.next=rear;
            //在这里判断下 m 前有没有元素
            if(m==1){
                head=mid;
            } else{
                preM.next=mid;
            }
        }
        if(count >= m && count <=n-1){
            //只有 mid 的位置大于 m 小于等于 n 才会将节点 next 域反转
            mid.next=pre;
        }
        //其他两个指针也向后移动
        pre=mid;
        mid=rear;
        count++;
    }
    return head;
}

func reverseBetween2(head *ListNode, m int, n int) *ListNode {
    dummyNode := &ListNode{
        Val:  -1,
        Next: head,
    }
    mpre := dummyNode //m 节点前的节点
    for i := m; i > 1; i-- {
        mpre = mpre.Next
    }
    pre := mpre
    cur := mpre.Next
    //  2   4
    //1 2 3 4 5
    for i := m; i <= n; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    mpre.Next.Next = cur //2.next=5
    mpre.Next = pre      //1.next=4
    return dummyNode.Next
}

//头插法
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    dummyNode := &ListNode{
        Val:  -1,
        Next: head,
    }
    mpre := dummyNode //m 节点前的节点
    for i := m; i > 1; i-- {
        mpre = mpre.Next
    }
    cur := mpre.Next
    //1 |2 3 4| 5
    for i := m; i < n; i++ {
        //除非 m=n=len 不然 next 肯定不为空，但是这种情况已经被循环的条件过滤了
        next := cur.Next
        cur.Next = next.Next
        next.Next = mpre.Next
        mpre.Next = next
    }
    return dummyNode.Next
}

Input: 
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].

Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

public static ListNode[] splitListToParts(ListNode root, int k) {
    //先要获取下链表的长度
    ListNode temp=root;
    ListNode next=root;
    ListNode [] result=new ListNode[k];
    int count=0;
    while(temp!=null){
        temp=temp.next;
        count++;
    }
    temp=root;
    //任意两部分差距不能大于 1，大的在前，小的在后面
    //其实就是对 count 进行分配
    //注意：有 null 的情况一定是 k>count 直接按 1 切分就完事了
    //k<count 的情况只要在 count/k 的前几个元素上加上 count/k 的余数就行了
    int size=count/k;
    int num=count%k;
    result[0]=root;
    int index=1;
    if(k<=count){
        for (int i=1;temp!=null && index < k;i++){
            next=temp.next;
            if(i<=(size+1)*num && i%(size+1)==0){
                //前几个 res 的分割点
                result[index++]=next;
                //切断
                temp.next=null;
            } else if(i>(size+1)*num && (i-num)%size==0){
                result[index++]=next;
                temp.next=null;
            }
            temp=next;
        }
    } else{
        //剩下的情况就是后面要补 null 的情况
        // 这里两种情况应该是可以合并的，但是 k>count num>0 懒得去抠边界
        for (int i=1;i<k;i++){
            if(temp==null){
                //这个 if 其实没必要
                result[i]=null;
            } else{
                next=temp.next;
                result[i]=next;
                temp.next=null;
                temp=next;
            }
        }
    }
    return result;
}

public ListNode partition(ListNode head, int x) {
    //先在头部加一个 dummy 节点统一操作
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=head;
    //分割点
    ListNode pre=cutNode=dummyNode;
    ListNode cur=head;
    int cut=0;
    while(cur!=null){
        if(cur.val>=x&&cut==0){
            //只会执行一次在找到第一个 val>=x 的节点的时候---保存分割点
            cutNode=pre;
            cut=1;
        } else if(cur.val<x && cut==1){
            //找到分割点后 遍历到 val<x 的节点的情况---将 cur 连接到 cutNode 的后面 处理好 cur 相邻的两个节点
            //先处理好 cur 相邻的节点
            pre.next=cur.next;
            //连接 cutNode
            cur.next=cutNode.next;
            cutNode.next=cur;
            //cutNode 后移
            cutNode=cur;
        }
        pre=cur;
        cur=cur.next;
    }
    return dummyNode.next
}

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA=headA;
    ListNode pB=headB;
    //计算两个链表长度然后计算差距然后向后对齐
    int lenA=0;
    int lenB=0;
    while(pA!=null){
        pA=pA.next;
        lenA++;
    }
    while(pB!=null){
        pB=pB.next;
        lenB++;
    }
    int dis=lenB>lenA?lenB-lenA:lenA-lenB;
    if(lenB>lenA){
        while(dis-->0){
            headB=headB.next;
        }
    } else{
        while(dis-->0){
            headA=headA.next;
        }
    }
    //不相等就一直向后移
    while(headA!=headB){
        //如果有一条为空说明没有交点
        if(headA.next==null){
            return null;
        }
        headA=headA.next;
        headB=headB.next;
    }
    return headA;
}

//方法二 
public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    //当一个指针到结尾时转到另一个链表头再向后移动 ，这样做的目的和就是可以直接消除链表之间的长度差，向后对齐，方法还是很巧妙的。
    ListNode pA=headA;
    ListNode pB=headB;
    if(headB==null || headA==null)
                 return null;
    //while(pA!=null && pB!=null ){
    while(pA!=pB){
        //要保证两个==null 的时候都只能执行一次不然如果没有交点就会死循环
        //改变 while 的条件
        //改变 pA，pB 跳转的条件
        //这样就可以保证最后没交点的时候 第二遍循环 pA 和 pB 最后会同时等于 null 会有出口不会死循环
        pA=pA==null?headB:pA.next;
        pB=pB==null?headA:pB.next;
    }
    return pA;
}

public boolean isPalindrome(ListNode head) {
    if(head==null || head.next==null){
        return true;
    }
    // 利用快慢指针找到中点
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null) {
        fast = fast.next.next == null ? fast.next : fast.next.next;
        slow = slow.next;
    }
    // 如果是偶数节点，slow 就是偏右的那个 奇数就是正中间的 奇数在正中间不用管
    // fast 是尾节点 1 1 1 1 1 1
    resverList(slow);
    //slow.next==null
    // check
    while (fast != null && head != null) {
        if (fast.val != head.val) {
            return false;
        }
        fast = fast.next;
        head = head.next;
    }
    return true;

}

public static void resverList(ListNode node) {
    ListNode cur = node;
    ListNode pre = null;
    ListNode next = node;
    while (cur != null) {
        next = next.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

public  static void deleteNodelow(ListNode node) {
    //思路就是和 node 后面的元素一直交换，就像冒泡排序一样
    ListNode next;
    ListNode temp=new ListNode(0);
    ListNode pre=temp;
    while(node.next!=null){
        next=node.next;
        if(node.next.next==null){
            pre=node;
        }
        //先保存最后一个节点前的节点
        //交换当前节点和后一个节点
        temp.val=node.val;
        node.val=next.val;
        next.val=temp.val;
        node=next;
    }
    pre.next=null;
}

  public  static void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;
  }

 public static ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode dummyHead = new ListNode(0);
        //再头接待你之前加了新的节点
        dummyHead.next = head;
        ListNode pre = dummyHead, cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                //不是相等的值就向后移动
                pre = cur;
            }
            cur = cur.next;
        }
        return dummyHead.next;
    }

//递归
public static ListNode removeElements2(ListNode head, int val){
    if (head == null)
       return null;
    //将下一个元素放进递归如果是==val 的就会把下一个的下一个元素返回连接到当前元素
    head.next = removeElements2(head.next, val);
    return head.val == val ? head.next : head;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head==null&&head.next==null) return null;
    //双指针 主要是头和尾的删除需要抠一下边界
    //  -1 | 1 2 3 4 5 6
    ListNode fast=head;
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=head;
    ListNode slow=dummyNode;
    //加了哑节点，直接先加 1
    int count=1;
    while(fast!=null){
        fast=fast.next;
        slow=count<n?slow:slow.next;
        count++;
        if(fast.next==null){
            //slow 到达需要删除的位置的前一个
            slow.next=slow.next.next;
            return dummyNode.next;
        }
    }
    return dummyNode.next;
}

public  static ListNode deleteDuplicates(ListNode head) {
    if(head==null)return null;
    //首先想到的思路是 3 指针，然后遍历的过程中后面的指针遇到==val 的情况就让后面的指针一直后移走到！=val
    //先添加个哑节点
    ListNode dummyNode=new ListNode(-1);
    dummyNode.next=head;
    ListNode cur=head;
    ListNode next=head.next;
    ListNode pre=dummyNode;
    while(next!=null){
        while(next.val==cur.val){
            next=next.next;
            if(next==null){
                pre.next=null;
                return dummyNode.next;
            }
            if(next.val!=cur.val){
                pre.next=next;
                //cur 跟上
                cur=next;
                break;
            }
        }
        //关键就是 pre 移动这里有坑 不能直接将 pre 移到 cur, 因为会有连续的连续存在
        pre=cur.next!=null&&cur.val==cur.next.val?pre:cur;
        cur=next;
        next=next.next;
    }
    return dummyNode.next;
}

public ListNode deleteDuplicates(ListNode head) {
    if(head==null || head.next==null) return head;
    if(head.val==head.next.val){
        while(head!=null && head.next!=null && head.val==head.next.val){
            head=head.next;
        }
        return deleteDuplicates(head.next); //去重
    }
    head.next=deleteDuplicates(head.next);
    return head;
}

输入：1->1->2
输出：1->2

输入：1->1->2->3->3
输出：1->2->3

//递归
public ListNode deleteDuplicates(ListNode head) {
    if(head==null || head.next==null) return head;
    ListNode node=deleteDuplicates(head.next);
    if(head.val==node.val) {
        head.next=node.next;
    }
    return head;
}

//迭代
public ListNode deleteDuplicates(ListNode head) {
    ListNode temp = head;
    while (temp != null){
        if (temp.next == null){
            break;
        }
        if (temp.next.val == temp.val){
            temp.next = temp.next.next;
        }else {
            temp = temp.next;
        }

    }
    return head;
}

 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]

 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeDuplicateNodes(head *ListNode) *ListNode {
    var set = make([]bool,20001)
    var dummyNode = &ListNode{Next:head}
    var pre = dummyNode
    for head!=nil{
        if !set[head.Val]{
            set[head.Val]=true
            pre=head
        }else{
            pre.Next=head.Next
        }
        head=head.Next
    }
    return dummyNode.Next
}

public static void reorderList(ListNode head) {
    if(head==null){
        return;
    }
    ListNode right = head;
    ListNode slow = head;
    // 1 1 1 1 1 1 1
    while (right.next != null) {
        right = right.next.next != null ? right.next.next : right.next;
        slow = slow.next;
    }
    // 从 slow 开始翻转
    res(slow);
    //左半部分
    ListNode left = head;
    //下一个节点
    ListNode rnext = right;
    ListNode lnext = left;
    // 1 2 3 4 5 6 7 8 
    // 1 8 2 7 3 6 4 5
    while (right != null && left != null) {
        // 要保存 right 的下一个节点 , left 也需要，不然无法导航到下一个节点
        lnext = lnext.next;
        rnext = rnext.next;
        // 偶数个数节点，如果遍历到 right 链表的最后一个节点
        // 偶数的话 right 链表会短一点 最后连接的时候
        // left: 1->2->3->4->5 right: 8->7->6->5   
        // 像这样会将 5 加到 left 的 4 和 5 之间，但是明显只有一个 5 这样添加就是有问题的
        if(right.next==null){
            //所以这里吧 lnext 赋值为 null, 后面就不会重复连接 5 这个节点
            lnext=null;
        }
        //奇数个数的时候这样连接没问题
        // 1 2 3 4 5 
        // 9 8 7 6 5
        //5.next=5
        left.next = right;
        //如果奇数个数到最后这一步 right 和 left 是同一个节点都为值是 5 的节点
        //所以这里下面的直接覆盖了上面的
        //5.next=null
        right.next = lnext;
        left = lnext;
        right = rnext;
    }
}

//反转
public static void res(ListNode node) {
    ListNode pre = null;
    ListNode cur = node;
    ListNode nex = node;
    while (cur != null) {
        nex = nex.next;
        cur.next = pre;
        pre = cur;
        cur = nex;
    }
}

输入： 1->2->4, 1->3->4
输出： 1->1->2->3->4->4

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp=new ListNode(0);
        ListNode res=temp;
        while(l1!=null&&l2!=null){
            if(l2.val<l1.val){
                temp.next=l2;
                l2=l2.next;
                temp=temp.next;
            }else{
                temp.next=l1;
                l1=l1.next;
                temp=temp.next;
            }
        }
        temp.next=l1==null?l2:l1;
        return res.next;
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummyNode=new ListNode(-1);
    mergeTwoLists(l1,l2,dummyNode);
    return dummyNode.next;
}

public void mergeTwoLists(ListNode l1, ListNode l2,ListNode res) {
    if(l1==null){
        res.next=l2;
        return;
    }

    if(l2==null){
        res.next=l1;
        return;
    }

    if(l1.val>l2.val){
        res.next=l2;
        mergeTwoLists(l1,l2.next,res.next);
    }else{
        res.next=l1;
        mergeTwoLists(l1.next,l2,res.next);
    }
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1==null) return l2;
    if(l2==null) return l1;
    ListNode dummyNode=new ListNode(-1);
    if(l1.val<l2.val){
        l1.next=mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next=mergeTwoLists(l1,l2.next);
        return l2;
    }
}

输入：
[
  1->4->5,
  1->3->4,
  2->6
]
输出：1->1->2->3->4->4->5->6

public ListNode mergeKLists(ListNode[] lists) {
    if(lists.length==0)return null;
    ListNode temp=lists[0];
    for (int i=0;i<lists.length-1;i++){
        temp=merge2List(temp,lists[i+1]);
    }
    return temp;
}

public static ListNode merge2List(ListNode headA,ListNode headB){
    ListNode dummyNode=new ListNode(-1);
    ListNode res=dummyNode;
    ListNode tempA=headA;
    ListNode tempB=headB;
    while(tempB!=null&&tempA!=null){
        if(tempB.val>tempA.val){
            res.next=tempA;
            tempA=tempA.next;
        } else{
            res.next=tempB;
            tempB=tempB.next;
        }
        res=res.next;
    }
    res.next=tempA==null?tempB:tempA;
    return dummyNode.next;
}

public ListNode mergeKLists2(ListNode[] lists) {
    if(lists.length==0)return null;
    return divide(lists,0,lists.length-1);
}

public static ListNode divide(ListNode[] lists,int left,int right){
    if(left>=right)return lists[left];
    int mid=left+((right-left)>>1);
    ListNode l = divide(lists,left,mid);
    ListNode r = divide(lists,mid+1,right);
    return merge2List(l,r);
}

public static ListNode merge2List(ListNode headA,ListNode headB){
    if(headA==null)return headB;
    if(headB==null)return headA;
    ListNode dummyNode=new ListNode(-1);
    ListNode res=dummyNode;
    ListNode tempA=headA;
    ListNode tempB=headB;
    while(tempB!=null&&tempA!=null){
        if(tempB.val>tempA.val){
            res.next=tempA;
            tempA=tempA.next;
        } else{
            res.next=tempB;
            tempB=tempB.next;
        }
        res=res.next;
    }
    res.next=tempA==null?tempB:tempA;
    return dummyNode.next;
}