2.1 链表开始!

反转链表

注意 while循环找的是cur.next还是cur 因为我这里在while内部已经让cur前进了我们需要比较的是cur

/**
     * 反转链表
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){//this
            ListNode temp = cur.next;
            cur.next = pre;
            //pre.next = cur.next;
            pre = cur;
            //让cur前进
            cur = temp;
        }
        return pre;
    }

找到链表中间值

如果链表长度是偶数我们返回的是靠左边的值

/**
     * 找到链表中点
     * @param head
     * @return
     */
    private ListNode findMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

141. 环形链表 判断是否是环形链表

public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }

707. 设计链表 链表设计

class MyLinkedList {
  // 结点类
  class Node {
        // 结点的值
        int val;
        // 指向下一个结点的指针(java中表现为下一个结点的引用)
        Node next;
        // 初始化 数据域val
        Node(int val) {
            this.val = val;
        }
    }

    // 记录头结点/指针
    Node head;
    // 记录链表的长度(元素的个数)
    int N;

    // 初始化  构造方法
    public MyLinkedList() {
        // 初始化长度
        N = 0;
        // 初始化头结点
        head = null;
    }

    // 获取指定 索引index 的结点
    // 注意点: 判断index的合法性(index<0 或 index>=N都是不合法的)
    public int get(int index) {
        // 如果index<0 或 index>=N
        if (index<0 || index>=N) {
            // 则返回-1
            return -1;
        }
        // 创建一个head的临时结点
        Node temp = head;
        // 通过循环,从头结点开始往后找,依次找i次,就可以找到对应的元素
        for (int i=0; i<index; i++) {
            temp = temp.next;
        }
        // 返回获取到的元素
        return temp.val;
    }

    // 头部插入
    public void addAtHead(int val) {
        // 创建一个新结点,保存 元素val
        Node temp = new Node(val);
        // 把 新结点的next指针 指向 原来的头结点
        temp.next = head;
        // 把新结点变为头结点
        head = temp;
        // 元素的个数+1
        N++;
    }

    // 尾部插入
    public void addAtTail(int val) {
        // 如果元素个数为0
        if (N == 0) {
            // 新元素成为头结点
            head = new Node(val);
            // 把头结点的next 指针 指向 null
            head.next = null;
        } else {
            // 创建一个head的临时结点
            Node temp = head;
            // 要找当前最后一个结点
            // 当结点的next 为null,表明找到尾结点
            while (temp.next != null) {
                temp = temp.next;
            }
            // 创建一个新结点,保存 元素val
            Node tail = new Node(val);
            // 作为即将要插入到最后(最后一个节点),不指向任何结点(指向null)
            tail.next = null;
            // 让当前最后一个结点的next 指向 新结点tail
            temp.next = tail;
        }
        // 元素的个数+1
        N++;
    }

    // 任意插入
    /* 注意点:
        ①判断index的值(小于等于0,采用头插法; 等于元素个数,采用尾插法)
        ②插入新的结点(先绑后面 再绑前面)
    */
    public void addAtIndex(int index, int val) {
        // 如果 输入的值index 大于 元素个数N
        if (index > N) {
            // 则结点将不会被插入
            return;
        }
        // 如果 输入的值index 小于等于 0
        if (index <= 0){
            // 则调用头插法
            addAtHead(val);
            // 这个return非常重要 要不然程序不会结束
            return; 
        }
        // 如果 输入的值index 等于 元素个数N
        if (index == N) {
            // 则调用尾插法
            addAtTail(val);
            // 这个return非常重要 要不然程序不会结束
            return;
        }
        // 创建一个head的临时结点
        Node temp = head;
        // 找到要插入结点的前驱
        // 寻找 索引index 之前的结点
        for (int i=0; i<index-1; i++) {
            temp = temp.next;
        }
        // 构建新的结点,让新的结点指向 索引index的结点
        Node addNode = new Node(val);
        // 新结点的next指针 指向 索引index的结点
        addNode.next = temp.next;
        // 让 索引index前驱的next指针 指向 新结点
        temp.next = addNode;
        // 元素的个数+1
        N++;
    }

    // 删除
    public void deleteAtIndex(int index) {
        // 如果 索引index = 0
        if(index == 0){
            // 直接把head的后驱变成头结点
            head = head.next;
            // 元素个数-1
            N--;
        // 如果 索引index满足条件 (>0 与 <N)
        }else if(index > 0 && index < N){
            // 创建一个head的临时结点
            Node temp = head;
            // 寻找 索引index的前驱
            for(int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            // 此时temp已经 变成 索引index的前驱;  temp后驱(temp.next) 变成 索引index; temp后驱的后驱(temp.next.next) 变成 索引i的后驱
            // 前驱的next指针 指向(链接) 索引index 的后驱[删除了 要删除的结点(索引i)]
            temp.next = temp.next.next;
            // 元素个数-1
            N--;
        }
    }
}

/**
 * MyLinkedList对象将被实例化并这样调用:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

class MyLinkedList {
    // 结点类
    class Node {
        // 结点的值
        int val;
        // 指向下一个结点的指针(java中表现为下一个结点的引用)
        Node next;
        // 初始化 数据域val
        Node(int val) {
            this.val = val;
        }
    }

    // 记录头结点/指针
    Node head;
    // 记录链表的长度(元素的个数) 因为下面要用到,用于判断index的合法性
    int N;

    // 初始化  构造方法
    public MyLinkedList() {
        // 初始化长度
        N = 0;
        // 初始化头结点 这里建立了一个虚拟头结点,这个节点指向头结点,
        // 现在因为没有头结点,所以指向null
        head = new Node(0);
    }

    // 获取指定 索引index 的结点
    public int get(int index) {
        //判断index的合法新
        if (index < 0 || index >= N) {
            return -1;
        }
        //建立一个临时节点来遍历链表找到目标位置的节点
        Node temp = this.head;
        for (int i = 0;i<=index;i++) {
            //不到目标位置,则临时节点向后移动,知道移动到指定位置
            temp = temp.next;
        }
        return temp.val;
    }

    // 头部插入
    public void addAtHead(int val) {
        this.addAtIndex(0,val);
    }

    // 尾部插入
    public void addAtTail(int val) {
        this.addAtIndex(N,val);
    }

    // 任意插入
    public void addAtIndex(int index, int val) {
        //判断index合法性 大于链表长度则直接返回
        if (index > N) {
            return;
        }
        //小于0代表插入到头结点,index改为0
        if (index < 0) {
            index = 0;
        }

        Node temp = head;
        //查找要插入节点的前驱
        //注意插入头结点的插入方法与普通节点不同,因为头结点没有前驱,
        //但是虚拟节点指向头结点,也就是说头结点的前驱是虚拟节点
        //所以头结点的插入也可以按照铺头节点的插入方法进行插入,
        //只要找到前驱即可
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        //找到后进行插入操作
        Node node = new Node(val);
        node.next = temp.next;
        temp.next = node;
        N++;
    }

    // 删除
    public void deleteAtIndex(int index) {
        //判断index合法性 大于链表长度或者小于0则直接返回
        if (index >= N || index < 0) {
            return;
        }

        Node temp = head;
        //这里跟上面一样,只要找到要删除位置的前驱指针,
        //因为有虚拟头指针的存在所以实际头指针也有前驱
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        //找到后进行插入操作
        temp.next = temp.next.next;
         N--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

203. 移除链表元素 删除节点

package linked_list;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class num_203_01 {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyListNode = new ListNode(0);
        dummyListNode.next = head;
        ListNode temp = dummyListNode;
        while (temp.next != null){
            if (temp.next.val == val){
                temp.next = temp.next.next;
            }else {
                temp = temp.next;
            }
        }
        return dummyListNode.next;
    }
}

删除结点的步骤
1 找到该结点的前一个结点
2 进行删除操作
Tip
删除头结点时另做考虑（由于头结点没有前一个结点）
添加一个虚拟头结点，删除头结点就不用另做考虑
关于递归操作：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/203-yi-chu-lian-biao-yuan-su-die-dai-di-eg52b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

206. 反转链表

双指针方法

定义两个指针： prepre 和 curcur ；prepre 在前 curcur 在后。 每次让 prepre 的 nextnext 指向 curcur ，实现一次局部反转 局部反转完成之后，prepre 和 curcur 同时往前移动一个位置 循环上述过程，直至 prepre 到达链表尾部

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //左指针cur
        ListNode cur = null;
        //右指针pre
        ListNode pre = head;
        //左右指针同时向前移动同时右指针pre.next指向cur
        while (pre != null){
            //暂存pre.next
            ListNode temp = pre.next;//需要注意我们两次用到了pre.next所有需要一个temp来暂存
            pre.next = cur;//这是第一个pre.next
            //cur向前一位即pre
            cur = pre;
            pre = temp;//这是第二个pre.next
        }
        return cur;
        }
}

递归方法 ~~难搞

思路: 递归

ListNode reverse(ListNode head) {

    if (head == null || head.next == null) {

        return head;

    }

    ListNode last = reverse(head.next);

    head.next.next = head;

    head.next = null;

    return last;

}

24. 两两交换链表中的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        //创建一个哑节点dummyHead
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode temp = dummyHead;

        while (temp.next!= null && temp.next.next != null){
        //dummyHead下一个
        ListNode node1 = temp.next;
        //下下个
        ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;

            //继续循环下去
            temp = node1;
        }
        return dummyHead.next;
    }
}

19 删除链表倒数第n个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //定义虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next=head;

        //定义start和end指针
        ListNode start = dummy;
        ListNode end = dummy;

        //先让end指针走n
        while(n > 0){
            end = end.next;
            n--;
        }
        //两指针同时走，知道end走到头
        while(end.next != null){
            end = end.next;
            start = start.next;

        }
        start.next = start.next.next;
        return dummy.next;
    }
}

面试题 02.07. 链表相交

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while (A != B){
            A = A != null ? A.next:headB;
            B = B != null ? B.next:headA;
        }
        return A;
    }
}

142. 环形链表 II

用哈希表存储每个节点一旦重复就说明存在环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode post = head;
        Set<Object> visted = new HashSet<>();
        while (post != null){
            if (visted.contains(post)){
                return post;
            }else {
                visted.add(post);
            }
            post = post.next;
        }
        return null;
    }
}

用快慢指针 labuladong的思路

ListNode detectCycle(ListNode head) {

    ListNode fast, slow;

    fast = slow = head;

    while (fast != null && fast.next != null) {

        fast = fast.next.next;

        slow = slow.next;

        if (fast == slow) break;

    }

    // 上面的代码类似 hasCycle 函数

    if (fast == null || fast.next == null) {

        // fast 遇到空指针说明没有环

        return null;

    }



    // 重新指向头结点

    slow = head;

    // 快慢指针同步前进，相交点就是环起点

    while (slow != fast) {

        fast = fast.next;

        slow = slow.next;

    }

    return slow;

}

234. 回文链表

首先通过找链表表中间值的方法找到链表的中心,这里注意 如果链表个数是奇数个那么让slow指针再往前走一步才能到达 其次通过反转链表的方法让后半部分反转 然后两部分链表进行比较

关于反转链表的图

/**
     * 反转链表的方法
     * @param head
     * @return
     */
    private ListNode reverse (ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){//注意这里判断条件不是cur.next,因为逻辑里面已经写了cur = next;
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;

            //让cur前进
            cur = next;
        }
        return pre;
    }

完整思路

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        //先找到中间值
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //判断奇数个数情况
        if (fast != null){
            slow = slow.next;//让slow再次向后移动一位
        }

        //生成两个链表
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null){//注意这里判断条不是right.next,因为逻辑里面已经写了right = right.next;
            if (left.val != right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    /**
     * 反转链表的方法
     * @param head
     * @return 返回反转后的链表
     */
    private ListNode reverse (ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;

            //让cur前进
            cur = next;
        }
        return pre;
    }
}

因为回文链表我们不需要遍历完链表只需要遍历right链表的长度即可此时的空间复杂度是o(1)

143. 重排链表

反转链表+找链表中间值+合并链表

package linked_list;



public class Num_143 {
    public void reorderList(ListNode head) {
        //链表中点
        ListNode mid = findMid(head);
        //链表的右半部分
        ListNode right = mid.next;
        //断掉两个链表的连接
        mid.next = null;
        //反转右部分 right就是反转后右部分的起点
        right = reverseList(right);
        //左部分的起点
        ListNode left = head;

        //将左右两个链表交叉合并
        while (right != null) {//这里只需要考虑right就行因为right我们是从前面截取的,指定要<=left
            //暂存left.next
            ListNode tempLeft = left.next;
            ListNode tempRight = right.next;

            left.next = right;
            left = tempLeft;//让left前进

            right.next = left;
            right = tempRight;//让temp前进
        }
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    private ListNode reverseList (ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            //pre.next = cur.next;
            pre = cur;

            //让cur前进
            cur = temp;
        }
        return pre;
    }

    /**
     * 找到链表中点
     * @param head
     * @return
     */
    private ListNode findMid (ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}