第9节.pptx

1：快慢指针

1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

  2. static class Node {
  3.     int value;
  4.     Node next;
  6.     public Node(int value) {
  7.         this.value = value;
  8.     }
  9. }
  11. //1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
  12. public static Node midOrUpMidNode(Node head) {
  13.     if (head == null || head.next == null || head.next.next == null) {
  14.         return head;
  15.     }
  16.     // 链表至少有3个节点
  17.     Node sPoint = head.next;
  18.     Node qPoint = head.next.next;
  20.     while (qPoint.next != null && qPoint.next.next != null) {
  21.         qPoint = qPoint.next.next;
  22.         sPoint = sPoint.next;
  23.     }
  24.     return sPoint;
  25. }
  27. public static Node test1(Node head) {
  28.     if (head == null) {
  29.         return head;
  30.     }
  31.     Node cur = head;
  32.     List<Node> list = new ArrayList<>();
  33.     while (cur != null) {
  34.         list.add(cur);
  35.         cur = cur.next;
  36.     }
  37.     return list.get((list.size() - 1) >> 1);
  38. }
  41. //2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
  42. public static Node midOrDownMidNode(Node head) {
  43.     if (head == null || head.next == null |) {
  44.         return head;
  45.     }
  46.     //链表至少有2个节点
  47.     Node sPoint = head.next;
  48.     Node qPoint = head.next;
  50.     while (qPoint.next != null && qPoint.next.next != null) {
  51.         qPoint = qPoint.next.next;
  52.         sPoint = sPoint.next;
  53.     }
  54.     return sPoint.next;
  55. }
  57. public static Node test2(Node head){
  58.     if (head == null) {
  59.         return head;
  60.     }
  61.     Node cur = head;
  62.     List<Node> list = new ArrayList<>();
  63.     while (cur != null) {
  64.         list.add(cur);
  65.         cur = cur.next;
  66.     }
  67.     return list.get(list.size() >> 1);
  68. }
  69. //3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
  70. public static Node midOrUpMidPreNode(Node head) {
  71.     if (head == null || head.next == null || head.next.next == null) {
  72.         return null;
  73.     }
  74.     // 至少3个节点
  75.     //链表至少有2个节点
  76.     Node sPoint = head;
  77.     Node qPoint = head.next.next;
  78.     while (qPoint.next != null && qPoint.next.next != null) {
  79.         qPoint = qPoint.next.next;
  80.         sPoint = sPoint.next;
  81.     }
  82.     return sPoint;
  83. }
  85. public static Node test3(Node head){
  86.     if (head == null||head.next==null||head.next.next==null) {
  87.         return null;
  88.     }
  89.     Node cur = head;
  90.     List<Node> list = new ArrayList<>();
  91.     while (cur != null) {
  92.         list.add(cur);
  93.         cur = cur.next;
  94.     }
  95.     return list.get((list.size()-3)>>1);
  96. }
  97. //4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
  98. public static Node midOrDownMidPreNode(Node head) {
  99.     if (head == null || head.next == null) {
  100.         return null;
  101.     }
  102.     if (head.next.next == null) {
  103.         return head;
  104.     }
  105.     // 至少3个节点
  106.     Node sPoint = head;
  107.     Node qPoint = head.next;
  108.     while (qPoint.next != null && qPoint.next.next != null) {
  109.         qPoint = qPoint.next.next;
  110.         sPoint = sPoint.next;
  111.     }
  112.     return sPoint;
  113. }
  115. public static Node test4(Node head){
  116.     if (head == null||head.next==null||head.next.next==null) {
  117.         return null;
  118.     }
  119.     Node cur = head;
  120.     List<Node> list = new ArrayList<>();
  121.     while (cur != null) {
  122.         list.add(cur);
  123.         cur = cur.next;
  124.     }
  125.     return list.get((list.size()-2)>>1);
  126. }

2 常见面试题

题目1 给定一个单链表的头节点head，请判断该链表是否为回文结构。

思路：
1）哈希表方法特别简单（笔试用）
2）改原链表的方法就需要注意边界了（面试用）

  1. public static class Node {
  2.     public int value;
  3.     public Node next;
  5.     public Node(int data) {
  6.         this.value = data;
  7.     }
  8. }
  10. // need n extra space
  11. public static boolean isPalindrome1(Node head) {
  12.     Stack<Node> stack = new Stack<Node>();
  13.     Node cur = head;
  14.     while (cur != null) {
  15.         stack.push(cur);
  16.         cur = cur.next;
  17.     }
  18.     while (head != null) {
  19.         if (head.value != stack.pop().value) {
  20.             return false;
  21.         }
  22.         head = head.next;
  23.     }
  24.     return true;
  25. }
  26. // need n extra space 使用List
  27. public static boolean isPalindromeList2(Node head) {
  28.     if (head == null | head.next == null) {
  29.         return true;
  30.     }
  32.     List<Node> list = new ArrayList<>();
  33.     Node cur = head;
  35.     while (cur != null) {
  36.         list.add(cur);
  37.         cur = cur.next;
  38.     }
  39.     cur = head;
  40.     for (int i = list.size() - 1; i >= 0; i--) {
  41.         if (list.get(i).value != cur.value) {
  42.             return false;
  43.         }
  44.         cur = cur.next;
  45.     }
  46.     return true;
  47. }
  49. // need n/2 extra space
  50. public static boolean isPalindrome2(Node head) {
  51.     if (head == null || head.next == null) {
  52.         return true;
  53.     }
  54.     Node right = head.next;
  55.     Node cur = head;
  56.     while (cur.next != null && cur.next.next != null) {
  57.         right = right.next;
  58.         cur = cur.next.next;
  59.     }
  60.     Stack<Node> stack = new Stack<Node>();
  61.     while (right != null) {
  62.         stack.push(right);
  63.         right = right.next;
  64.     }
  65.     while (!stack.isEmpty()) {
  66.         if (head.value != stack.pop().value) {
  67.             return false;
  68.         }
  69.         head = head.next;
  70.     }
  71.     return true;
  72. }
  74. // need O(1) extra space
  75. public static boolean isPalindromeList(Node head) {
  76.     if (head == null || head.next == null) {
  77.         return true;
  78.     }
  79.     // 至少2个节点
  80.     Node n1 = head;
  81.     Node n2 = head;
  82.     // n1 ，链表长度为奇数时，为中点；链表长度为偶数时，为上中点
  83.     while (n2.next != null && n2.next.next != null) {
  84.         n2 = n2.next.next;
  85.         n1 = n1.next;
  86.     }
  88.     n2 = n1.next;
  89.     n1.next = null;
  90.     Node n3 = null;
  91.     while (n2 != null) {
  92.         n3 = n2.next;
  93.         n2.next = n1;
  94.         n1 = n2;
  95.         n2 = n3;
  96.     }
  98.     // n1 是最后一个节点，n3 是最后一个节点
  99.     n3 = n1;
  100.     n2 = head;
  102.     boolean ans = true;
  104.     while (n1 != null && n2 != null) {
  105.         if (n1.value != n2.value) {
  106.             ans = false;
  107.             break;
  108.         }
  109.         n1 = n1.next;
  110.         n2 = n2.next;
  111.     }
  112.     // n1 为倒数第2个节点
  113.     n1 = n3.next;
  114.     n3.next = null;
  115.     while (n1 != null) {
  116.         n2 = n1.next;
  117.         n1.next = n3;
  118.         n3 = n1;
  119.         n1 = n2;
  120.     }
  121.     return ans;
  122. }

题目2：将单向链表按某值划分成左边小、中间相等、右边大的形式

思路：
1）把链表放入数组里，在数组上做partition（笔试用）
2）分成小、中、大三部分，再把各个部分之间串起来（面试用）

  1. static class Node {
  2.     int value;
  3.     Node next;
  5.     public Node(int value) {
  6.         this.value = value;
  7.     }
  8. }
  10. // 法1 分成小、中、大三部分，再把各个部分之间串起来（面试用）
  11. public static Node smallEqualBig(Node head, int k) {
  12.     // 只有0、1个节点情况下直接返回
  13.     if (head == null || head.next == null) {
  14.         return head;
  15.     }
  16.     //至少2个节点的情况
  18.     Node smallHead = null;
  19.     Node smallTail = null;
  20.     Node equalHead = null;
  21.     Node equalTail = null;
  22.     Node bigHead = null;
  23.     Node bigTail = null;
  24.     Node next = null;
  27.     while (head != null) {
  28.         next = head.next;
  29.         head.next = null;
  30.         if (head.value < k) {
  31.             if (smallHead == null) {
  32.                 smallHead = head;
  33.             } else {
  34.                 smallTail.next = head;
  35.             }
  36.             smallTail = head;
  37.         } else if (head.value == k) {
  38.             if (equalHead == null) {
  39.                 equalHead = head;
  40.             } else {
  41.                 equalTail.next = head;
  42.             }
  43.             equalTail = head;
  44.         } else {
  45.             if (bigHead == null) {
  46.                 bigHead = head;
  47.             } else {
  48.                 bigTail.next = head;
  49.             }
  50.             bigTail = head;
  51.         }
  52.         head = next;
  53.     }
  55.     if (smallTail != null) {
  56.         smallTail.next = equalHead;
  57.         equalTail = equalTail == null ? smallTail : equalTail;
  58.     }
  60.     if (equalTail != null) {
  61.         equalTail.next = bigHead;
  62.     }
  63.     return smallHead != null ? smallHead : (equalHead != null ? equalHead : bigHead);
  64. }
  67. // 法2 把链表放入数组里，在数组上做partition（笔试用）
  68. public static Node smallEqualBig2(Node head, int k) {
  69.     if (head == null || head.next == null) {
  70.         return head;
  71.     }
  73.     ArrayList<Node> list = new ArrayList<>();
  74.     while (head != null) {
  75.         list.add(head);
  76.         head = head.next;
  77.     }
  79.     partition(list, k);
  82.     for (int i = 0; i < list.size(); i++) {
  83.         head = list.get(i);
  84.         if (i == list.size() - 1) {
  85.             head.next = null;
  86.         } else {
  87.             head.next = list.get(i + 1);
  88.         }
  89.     }
  90.     return list.get(0);
  91. }
  93. private static void partition(ArrayList<Node> list, int k) {
  94.     int smallR = -1;
  95.     int bigL = list.size() - 1;
  97.     for (int i = 0; i <= bigL; ) {
  98.         if (list.get(i).value < k) {
  99.             swap(list, ++smallR, i++);
  100.         } else if (list.get(i).value == k) {
  101.             i++;
  102.         } else {
  103.             swap(list, bigL--, i);
  104.         }
  105.     }
  106. }
  108. private static void swap(ArrayList<Node> list, int i, int j) {
  109.     Node tmp = list.set(i, list.get(j));
  110.     list.set(j, tmp);
  111.   }

题目3：链表的复制，并返回复制的新链表的头节点。

leetcode : https://leetcode.com/problems/copy-list-with-random-pointer/
一种特殊的单链表节点类描述如下
class Node {
int value;
Node next;
Node rand;
Node(intval) { value = val; }
}
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】
时间复杂度O(N)，额外空间复杂度O(1) 

static class Node {
    int value;
    Node next;
    Node random;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Node node = (Node) o;
        return value == node.value && Objects.equals(next, node.next) && Objects.equals(random, node.random);
    }

    @Override
    public int hashCode() {
        return Objects.hash(value, next, random);
    }
}

public static Node copyListWithRandom(Node head) {
    // 0、1个节点 直接返回
    if (head == null) {
        return head;
    }
    Node cur = head;
    Node next = null;
    while (cur != null) {
        Node newNode = new Node(cur.value);
        next = cur.next;
        cur.next = newNode;
        newNode.next = next;
        cur = next;
    }

    cur = head;
    Node random = null;
    while (cur != null) {
        random = cur.random;
        cur.next.random = random != null ? random.next : null;
        cur = cur.next.next;
    }

    Node ans = head.next;
    Node ansCur = ans;
    cur = head;
    while (cur != null) {
        next = cur.next.next;
        cur.next = next;
        ansCur.next = next != null ? next.next : null;
        cur = next;
        ansCur = ansCur.next;
    }
    return ans;
}

// 法2 使用容器
public static Node copyListWithRandom2(Node head) {
    // key 老节点
    // value 新节点
    HashMap<Node, Node> map = new HashMap<>(16);
    Node cur = head;
    while (cur != null) {
        map.put(cur, new Node(cur.value));
        cur = cur.next;
    }
    cur = head;
    while (cur != null) {
        // cur 老
        // map.get(cur) 新
        // 新.next ->  cur.next克隆节点找到
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}

题目4 返回2个可能有环的链表相交的第一个节点

给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null
【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。 

public static Node findFirstIntersectNode(Node head1, Node head2) {
    // 两个链表都为空
    if (head1 == null || head2 == null) {
        return null;
    }
    // 两个链表都不为空

    Node loop1 = isLoop(head1);
    Node loop2 = isLoop(head2);
    if (loop1 == null && loop2 == null) {
        return noLoopIntersect(head1, head2);
    } else if (loop1 == null ^ loop2 == null) {
        return oneLoopIntersect(head1, head2);
    } else {
        return twoLoopIntersect(head1, head2);
    }
}

// 判断链表是否有环，有环则返还进入环的节点，无环则返回null

private static Node isLoop(Node head) {
    if (head == null || head.next == null || head.next.next == null) {
        return null;
    }
    Node slow = head.next;
    Node fast = head.next.next;

    // 从循环里出来时,slow==fast
    while (slow != fast) {
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    fast = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}
/*
* 两个可能有环的链表相交，有以下几种情况：
* 1 两个无环链表不相交
* 2 两个无环链表相交
* 3 一个有环、一个无环 不可能相交
* 4 两个有环链表不相交
* 5 两个有环链表相交
*   i 相交节点在第一个入环节点之前
*   ii 相交节点环上
* */

//  返回两个无环链表相交节点，不相交返回null（情况1、2)

private static Node noLoopIntersect(@NotNull Node head1, @NotNull Node head2) {
    Node end1 = head1;
    Node end2 = head2;
    //至少有一个节点
    int size1 = 1;
    int size2 = 1;
    while (end1.next != null) {
        size1++;
        end1 = end1.next;
    }
    while (end2.next != null) {
        size2++;
        end2 = end2.next;
    }
    // 两个无环链表相交，那么最后一个节点一定相同，不同则表示两个链表不相交
    if (end1 != end2) {
        return null;
    }
    // end1节点指向长的那个链表，end2指向短的那个链表
    end1 = size1 > size2 ? head1 : head2;
    end2 = end1 == head1 ? head2 : head1;

    for (int i = 0; i < Math.abs(size1 - size2); i++) {
        end1 = end1.next;
    }

    while (end1 != end2) {
        end1 = end1.next;
        end2 = end2.next;
    }
    return end1;
}

//  一个有环，一个无环,不可能相交(情况3)

private static Node oneLoopIntersect(Node head1, Node head2) {
    return null;
}

// 返回两个有环链表相交第一个节点，不相交返回null(情况4、5)

private static Node twoLoopIntersect(Node head1, Node head2) {
    Node loopNode1 = isLoop(head1);
    Node loopNode2 = isLoop(head2);
    // 相交节点在第一个入环节点之前
    if (loopNode1 == loopNode2) {
        // 将第一个入环节点当成链表最后一个节点，类似情况2
        Node end1 = head1;
        Node end2 = head2;
        int n = 0;
        while (end1 != loopNode1) {
            n++;
            end1 = end1.next;
        }
        while (end2 != loopNode2) {
            n--;
            end2 = end2.next;
        }
        // end1 指向长的链表
        end1 = n > 0 ? head1 : head2;
        end2 = end1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            end1 = end1.next;
            n--;
        }
        while (end1 != end2) {
            end1 = end1.next;
            end2 = end2.next;
        }
        return end1;
    } else {
        Node loopNodeCur = loopNode1.next;
        while (loopNodeCur != loopNode1) {
            // 相交节点在环上
            if (loopNodeCur == loopNode2) {
                return loopNode1;
            }
            loopNodeCur = loopNodeCur.next;
        }
        // 不相交
        return null;
    }
}