LeetCode 1-10题

BM1 反转链表

给定一个单链表的头结点pHead（该头节点是有值的,比如在下图,它的val是1）,长度为n,反转该链表后,返回新链表的表头.
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ,时间复杂度 O(n) .
如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}.
输入：{1,2,3}
返回值：{3,2,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) {
    
        if(head==null){
    
            return head;
        }
        ListNode pre = null;
        ListNode pHead = head;
        ListNode pNext;
        while(pHead!=null){
    
            pNext = pHead.next;
            pHead.next = pre;
            pre = pHead;
            pHead = pNext;
        }
        return pre;
    }
}

BM2 链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n),空间复杂度 O(1).
例如：给出的链表为 1→2→3→4→5→NULL, m=2,n=4, 返回 1→4→3→2→5→NULL.
数据范围： 链表长度 0<size≤1000,0<m≤n≤size,链表中每个节点的值满足 ∣val∣≤1000
要求：时间复杂度 O(n) ,空间复杂度 O(n)
进阶：时间复杂度 O(n),空间复杂度 O(1)
输入：{1,2,3,4,5},2,4
返回值：{1,4,3,2,5}

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */
    public ListNode reverseBetween (ListNode head, int m, int n) {
    
        // write code here
        if(head==null || m==n){
    
            return head;
        }
        ListNode pHead = new ListNode(-1);
        ListNode pre = head;
        if(m==1){
    
            pHead.next = pre;
            ListNode temp = pHead.next;
            for(int i=1; i<n; i++){
    
                temp = temp.next;
            }
            ListNode post = temp.next;
            temp.next = null;
            temp = pHead.next;
            temp = Reverse(temp);
            head = temp;
            while(temp.next!=null){
    
                temp = temp.next;
            }
            temp.next = post;
            return head;
        } else{
    
            for(int i=1; i<m-1; i++){
    
                pre = pre.next;
            }
            pHead.next = pre.next;
            ListNode temp = pHead.next;
            pre.next = null;
            for(int i=m; i<n; i++){
    
                temp = temp.next;
            }
            ListNode post = temp.next;
            temp.next = null;
            temp = pHead.next;
            // 反转
            temp = Reverse(temp);
            pre.next = temp;
            while(temp.next!=null){
    
                temp = temp.next;
            }
            temp.next = post;
            return head;
        }
        
    }
    
    public ListNode Reverse (ListNode head){
    
        if(head==null){
    
            return head;
        }
        ListNode pre = null;
        ListNode post;
        while(head!=null){
    
            post = head.next;
            head.next = pre;
            pre = head;
            head = post;
        }
        return pre;
    }
}

BM3 链表中的节点每k个一组翻转

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身.
数据范围：0≤n≤2000 , 1≤k≤2000 ,链表中每个元素都满足 0≤val≤1000
要求空间复杂度 O(1),时间复杂度 O(n)
例如：
给定的链表是 1→2→3→4→5
对于 k = 2 , 你应该返回 2→1→4→3→5
对于 k = 3 , 你应该返回 3→2→1→4→5
输入：{1,2,3,4,5},2
返回值：{2,1,4,3,5}

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */
    public ListNode reverseKGroup (ListNode head, int k) {
    
        // write code here
        ListNode temp = new ListNode(-1);
        ListNode ppp = temp;
        int i = 0;
        while(head!=null){
    
            ListNode node = new ListNode(-1);
            node.next = head;
            ListNode pre = node.next;
            for(int j=1; j<=k & node.next!=null; j++){
    
                node = node.next;
                i = i + 1;
            }
            head = node.next;
            if(i%k==0){
    
// System.out.println(i);
                node.next = null;
                ListNode p = reverse(pre);
                temp.next = p;
                while(p.next!=null){
    
                    p = p.next;
                }
                temp = p;
            } else{
    
                temp.next = pre;
            }
        }
// ListNode temp = reverse(head);
        return ppp.next;
    }
    
     public ListNode reverse(ListNode head){
    
         if(head==null){
    
             return head;
         }
         ListNode pre = null;
         ListNode post;
         while(head!=null){
    
             post = head.next;
             head.next = pre;
             pre = head;
             head = post;
         }
         return pre;
     }
}

BM4 合并两个排序的链表

输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的.
数据范围： 0≤n≤1000,−1000≤节点值≤1000
要求：空间复杂度 O(1),时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},
或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所以对应的输出为{-1,1,2,3,4,4}
输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}

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) {
    
        ListNode p = new ListNode(-1);
        ListNode temp = p;
        while(list1!=null & list2!=null){
    
            if(list1.val>list2.val){
    
                p.next = list2;
                list2 = list2.next;
                p = p.next;
            } else{
    
                p.next = list1;
                list1 = list1.next;
                p = p.next;
            }
        }
        while(list1==null & list2!=null){
    
            p.next = list2;
            list2 = list2.next;
            p = p.next;
        }
        while(list2==null & list1!=null){
    
            p.next = list1;
            list1 = list1.next;
            p = p.next;
        }
        return temp.next;
    }
}

BM5 合并k个已排序的链表

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点.
数据范围：节点总数满足 0≤n≤100000 ,链表个数满足 1≤k≤100000 ,每个链表的长度满足 1≤len≤200 ,每个节点的值满足 ∣val∣<=1000
要求：时间复杂度 O(nlogk)
输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}

import java.util.*;
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
    
// if(lists.isEmpty()){
    
// ListNode node = new ListNode(-1);
// node = node.next;
// return node;
// }
// ListNode node = lists.get(0);
// for(int i=1; i<lists.size(); i++){
    
// node = merge(node, lists.get(i));
// }
        // 0 - lists.size()-1
        return mergeList(lists, 0, lists.size()-1);
    }
    
    // 归并排序
    public ListNode mergeList(ArrayList<ListNode> lists, int left, int right){
    
        if(left==right)
            return lists.get(left);
        if(left>right)
            return null;
        int mid = (left+right)/2;
        return merge(mergeList(lists, left, mid), mergeList(lists, mid+1, right));
    }
    
    public ListNode merge(ListNode list1, ListNode list2) {
    
        ListNode p = new ListNode(-1);
        ListNode temp = p;
        while(list1!=null & list2!=null){
    
            if(list1.val>=list2.val){
    
                p.next = list2;
                list2 = list2.next;
                p = p.next;
            } else{
    
                p.next = list1;
                list1 = list1.next;
                p = p.next;
            }
        }
        if(list1==null & list2!=null){
    
            p.next = list2;
        }
        if(list2==null & list1!=null){
    
            p.next = list1;
        }
        return temp.next;
    }
}

BM6 判断链表中是否有环

判断给定的链表中是否有环.如果有环则返回true,否则返回false.
数据范围：链表长度 0≤n≤10000,链表中任意节点的值满足 ∣val∣<=100000
要求：空间复杂度 O(1),时间复杂度 O(n)
输入分为两部分,第一部分为链表,第二部分代表是否有环,然后将组成的head头结点传入到函数里面.-1代表无环,其它的数字代表有环,这些参数解释仅仅是为了方便读者自测调试.实际在编程时读入的是链表的头节点.
输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表,第二部分的1表示,-4到位置1（注：头结点为位置0）,即-4->2存在一个链接,组成传入的head为一个带环的链表,返回true

import java.util.*;
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        if(head==null || head.next==null || head.next.next==null){
    
            return false;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        while(p1!=null){
    
            if(p1==p2){
    
                return true;
            }
            if(p2==null || p2.next==null){
    
                return false;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return false;
    }
}

BM7 链表中环的入口结点

给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null.
数据范围： n≤10000,1<=结点值<=10000
要求：空间复杂度 O(1),时间复杂度 O(n)
输入描述：
输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可,我们后台程序会打印这个结点对应的结点值;若没有,则返回对应编程语言的空结点即可.
输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口结点,我们后台程序会打印该环形链表入口结点对应的结点值,即3

import java.util.*;
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
    

    public ListNode EntryNodeOfLoop(ListNode pHead) {
    
        if(pHead==null || pHead.next==null || pHead.next.next==null){
    
            return null;
        }
        ListNode p1 = pHead;
        ListNode p2 = pHead.next;
        while(p1!=null){
    
            if(p1==p2){
    
                if(pHead==p1.next){
    
                    return pHead;
                }
                pHead = pHead.next;
                p1 = p1.next;
                p2 = p2.next;
            } else{
    
                if(p2==null || p2.next==null){
    
                    return null;
                }
                p1 = p1.next;
                p2 = p2.next.next;
            }
        }
        return null;
    }
}

BM8 链表中倒数最后k个结点

输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点.
如果该链表长度小于k,请返回一个长度为 0 的链表.
数据范围：0≤n≤100000
0≤ai≤1000000000, 0≤k≤1000000000
要求：空间复杂度 O(n),时间复杂度 O(n)
进阶：空间复杂度 O(1),时间复杂度 O(n)
输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4,系统会打印后面所有的节点来比较.

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */

public class Solution {
    
    /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */
    public ListNode FindKthToTail (ListNode pHead, int k) {
    
        if(pHead==null || k==0){
    
            return null;
        }
        // write code here
        ListNode p = pHead;
        int i = 1;
        while(i<k){
    
            pHead = pHead.next;
            if(pHead==null){
    
                return null;
            }
            i = i + 1;
        }
        while(pHead.next!=null){
    
            p = p.next;
            pHead = pHead.next;
        }
        return p;
    }
}

BM9 删除链表的倒数第n个节点

给定一个链表,删除链表的倒数第 n 个节点并返回链表的头指针
例如,给出的链表为: 1→2→3→4→5, n=2.
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.
数据范围： 链表长度 0≤n≤1000,链表中任意节点的值满足 0≤val≤100
要求：空间复杂度 O(1),时间复杂度 O(n)
备注：题目保证 n 一定是有效的
输入：{1,2},2
返回值：{2}

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */
    public ListNode removeNthFromEnd (ListNode head, int n) {
    
        if(n==1 && head.next==null){
    
            return head.next;
        }
        // write code here
        ListNode temp = head;
        ListNode pre = head;
        int i = 1;
        while(i<n){
    
            head = head.next;
            i = i + 1;
        }
        if(head.next==null){
    
            return pre.next;
        }
        while(head.next.next!=null){
    
            head = head.next;
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return pre;
    }
}

BM10 两个链表的第一个公共结点

输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空.（注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的）
数据范围： n≤1000
要求：空间复杂度 O(1),时间复杂度 O(n)
输入描述：
输入分为是3段,第一段是第一个链表的非公共部分,第二段是第二个链表的非公共部分,第三段是第一个链表和第二个链表的公共部分. 后台会将这3个参数组装为两个链表,并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面,用户得到的输入只有pHead1和pHead2.
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点,后台会打印以该节点为头节点的链表.
输入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分,第二个参数{4,5}代表是第二个链表非公共部分,最后的{6,7}表示的是2个链表的公共部分, 这3个参数最后在后台会组装成为2个两个无环的单链表,且是有公共节点的

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) {
    
        if(pHead1==null || pHead2==null){
    
            return null;
        }
        int sum1 = 1;
        // 长链表
        ListNode p1 = pHead1;
        while(pHead1.next!=null){
    
            pHead1 = pHead1.next;
            sum1 = sum1 + 1;
        }
        int sum2 = 1;
        // 短链表
        ListNode p2 = pHead2;
        while(pHead2.next!=null){
    
            pHead2 = pHead2.next;
            sum2 = sum2 + 1;
        }
        int sum3 = 0;
        if(sum1<sum2){
    
            ListNode p = p1;
            p1 = p2; 
            p2 = p;
            sum3 = sum2 - sum1;
        } else{
    
            sum3 = sum1 - sum2;
        }
        sum1 = 1;
        while(sum1<=sum3){
    
            p1 = p1.next;
            sum1 = sum1 + 1;
        }
        while(p1!=null){
    
            if(p1==p2){
    
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
}