ListNode-easy系列题

  1. Delete Node in a Linked List(node.val = node.next.val; node.next = node.next.next;连接跳过即可)
  2. Remove Nth Node From End of List(要删除尾巴指定位置的节点,首先是先找到它,快慢指针的思想在于,先让两个指针起点一下,然后快指针先走N步,然后两者一起走,当快指针走到头时,慢指针所在的位置就是我们想要的位置,这么麻烦的原因也是因为listnode没有按照序号遍历的功能,只能很原始的去找)
  3. Reverse Linked List(一个指针一直指在新链接的头上,另外一个不断是去编制,注意编织的顺序,让head及时滑向下一个)
  4. Merge Two Sorted Lists(合并两个有序链表,考虑4中情况,其实就是归并排序的merge子函数,没啥,递归解决)
  5. Palindrome Linked List(思路是快慢指针进行二分,注意有快指针的话,判断条件fast!=null&&fast.next!=null,同时这道题也要注意奇偶数的判断,有一个额外的判断条件让slow越过那个奇数值)
  6. Linked List Cycle(还是利用了快慢指针的思想,要是存在圈,快慢指针一定会相遇导致slow==fast )

    ListNode-middle系列题

    Add Two Numbers

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    
    class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);//结果指针,表示答案,它不能滑动
        ListNode point = result;//苦力指针,用来滑动编制
        int temp = 0;//进位标志位
        while(l1 != null || l2 != null || temp != 0){
    
            if (l1!=null){
                temp += l1.val;
                l1 = l1.next;
            }
            if (l2!=null){
                temp += l2.val;
                l2 = l2.next;
            }
            ListNode tempnode = new ListNode(temp%10);//取新节点
            point.next = tempnode;//编制
            point = point.next;//编制完移动
            temp = temp/10;//进位标志位更新
        }
        return result.next;//去掉头部无用节点返回
    }
    }

    这道题第一感觉难在进位上,还有就是要考虑到两条链表不是一样长的时候的情形。对于链表的编制,往往都需要一个钉在开头的指针和一个不断编制的苦力指针(苦力指针基本上要执行node1.next=node2;node = node.next)。

    Odd Even Linked List

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    
    class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head!=null){
            ListNode odd = head, even = head.next, evenhead = even;//奇数偶数各一个起始位,并且保留偶数起始位,用于之后的连接
            while(even!=null&&even.next!=null){//只要while里面涉及到了node = node.next的话,就需要进行next判断,之前我是觉得fast才需要的
                odd.next = odd.next.next;//奇数编制
                odd = odd.next;//奇数滑动
                even.next = even.next.next;//偶数编制
                even = even.next;//偶数滑动
            }
            odd.next = evenhead;//两条连接进行合并
        }
        return head;
    }
    }

    奇偶数的分开再编制,思路简单,但是这道题没有新建一个node来表示答案,而是直接用head返回,之后要考虑下什么时候需要新建node,什么时候可以返回node。

    Intersection of Two Linked Lists

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    
    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode pointA = headA;
        ListNode pointB = headB;
        while(pointA!=pointB){
            pointA = pointA == null ? headB : pointA.next;
            pointB = pointB == null ? headA : pointB.next;
        }
        return pointA;
    }
    }

    问题在于两条链表的长度不同的话,无法进行比较,否则只需要进行node1==node2指针比较即可,那么问题在于长度 不同,可以让链表1连上链表2;链表2连上链表1,这样长度就一样了,之后再判断就可以了。

    ListNode-hard系列题

    Merge k Sorted Lists

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    
    class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return sortByPartition(lists, 0, lists.length-1);
    }
    
    private ListNode sortByPartition(ListNode[] lists, int start, int end){
        /*
        * 递归先确定结束条件
        * */
        if (start == end){
            return lists[start];
        }
        /*
        * 经典的分治理念,切半,递归递归,合并
        * */
        int mid = start+(end-start)/2;
        ListNode left = sortByPartition(lists, start, mid);
        ListNode right = sortByPartition(lists, mid+1, end);
        return merge(left,right);
    }
    
    private ListNode merge(ListNode left, ListNode right){
        /*
        * 同样是递归,先要确定结束条件
        * */
        if (left == null || right == null){
            return left == null ? right : left;
        }
        /*
        * 链表合并总是要有连接的过程的,这边需要额外注意
        * */
        if (left.val<right.val){
            left.next = merge(left.next,right);
            return left;
        }
        else {
            right.next = merge(left,right.next);
            return right;
        }
    }
    }

    这不就是归并排序嘛,之前的middle难度的merge双lists算是merge的练习的话,这个就是merge sort的链表版本,区别是归并排序merge的是等长的数组,这边merge的是一条条的链表,对于链表合并的优先性,这边取的是二分法,有点不确定这和挨个合并的区别;还有一点是排序版本的么merge需要(lo,mid(是因为要判断用尽),hi)而listnode版本的只需要(list1,list2)。

    Sort List

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head, pre = head;
        /*
         * 这个相当于是二分啦
         * */
        while (fast != null && fast.next != null) {//有fast的存在,判断的时候需要有两个判断条件
            pre = slow;//这个pre用来切数组,周末一定要把链表的
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        return merge(left, right);
    }
    
    private ListNode merge(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        if (left.val < right.val) {
            left.next = merge(left.next, right);
            return left;
        } else {
            right.next = merge(left, right.next);
            return right;
        }
    }
    }

    归并和链表也太相配了吧,merge部分还是一样的,主要是sort部分,结合之前总结的快慢指针代替二分的方法,pre用来断开链接。

    Copy List with Random Pointer

    ```java public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if (head == null){ return null; } Map map = new HashMap();

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    /*
    * 节点意义复制到map中
    * */
    RandomListNode point = head;
    while(point!=null){
        map.put(point,new RandomListNode(point.label));
        point = point.next;
    }
    /*
    * 指针重新指向开头的地方
    * */
    point = head;
    while(point!=null){
        map.get(point).next = map.get(point.next);
        map.get(point).random = map.get(point.random);
        point = point.next;
    }
    return map.get(head);

    } } ``` 链表的深拷贝,不是很懂他的原理,之后如果遇到了再看看吧。