面试算法大全-链表总结

系统管理员 2022-10-17 13:49 222阅读 0赞

## 2、链表 ##

链表常用的有 3 类： 单链表、双向链表、循环链表。

![img][]

### 2.1 链表的概念和实现 ###

#### 2.1.1 单项链表 ####

节点定义

private static class Node<E> {
        
        E item;
        Node<E> next;
    
        Node(E element, Node<E> next) {
        
            this.item = element;
            this.next = next;
        }
    }

单链表实现

public class LinkList {
        
        private Object data;
        private LinkList next;
    
        public LinkList() {
        
        }
    
        public LinkList(Object data) {
        
            this.data = data;
            this.next = null;
        }
    
        public Object getData() {
        
            return data;
        }
    
        public void setData(Object data) {
        
            this.data = data;
        }
    
        public LinkList getNext() {
        
            return next;
        }
    
        public void setNext(LinkList next) {
        
            this.next = next;
        }
    
        @Override
        public String toString() {
        
            return "LinkList{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    
        @Override
        public boolean equals(Object o) {
        
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            LinkList linkList = (LinkList) o;
            return data.equals(linkList.data);
        }
    
        @Override
        public int hashCode() {
        
            return Objects.hash(data, next);
        }
    }

链表基本操作

/**
         * 添加数据
         *
         * @param data
         */
        public static boolean addNode(Object data) {
        
            LinkList newNode = new LinkList(data);// 实例化一个节点
            if (head == null) {
        
                head = newNode;
                return true;
            }
            LinkList tmp = head;
            while (tmp.getNext() != null) {
        
                tmp = tmp.getNext();
            }
            tmp.setNext(newNode);
            return true;
        }
    
        /**
         * 删除节点：根据数据查询
         *
         * @param data
         * @return
         */
        public static boolean removeNode(Object data) {
        
            if (head == null) {
        
                System.out.println("当前数据为空");
                return false;
            }
            if (head.getData().equals(data)) {
        
                //判断如果是头节点的话 将下一个节点变成头节点  该节点的node设null
                head = head.getNext();
                return true;
            }
            LinkList preNode = head;
            LinkList tmpNode = head.getNext();
            while (tmpNode != null) {
        
                if (tmpNode.equals(data)) {
        
                    //如果不是头节点，就将上一个node指向下一个
                    preNode.setNext(tmpNode.getNext());
                    return true;
                }
                preNode = tmpNode;
                tmpNode = tmpNode.getNext();
            }
            return false;
        }
    
        /**
         * 遍历链表
         */
        public static void printList() {
        
            LinkList tmpNode = head;
            while (tmpNode != null) {
        
                System.out.println(tmpNode.getData());
                tmpNode = tmpNode.getNext();
            }
        }

#### 2.1.2 双向链表 ####

双向链表节点

private static class Node<E> {
        
        E item;
        Node<E> next;
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) {
        
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

JDK双向链表实现

package java.util;
    
    import java.util.function.Consumer;
    
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        
        // 链表大小
        transient int size = 0;
    
        // 链表头部
        transient Node<E> first;
    
        // 链表尾部
        transient Node<E> last;
    
        public LinkedList() {
        
        }
    
        public LinkedList(Collection<? extends E> c) {
        
            this();
            addAll(c);
        }
    
        // 获取头部元素
        public E getFirst() {
        
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
    
        // 获取尾部元素
        public E getLast() {
        
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
    
        // 删除头部元素
        public E removeFirst() {
        
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    
        // 删除尾部元素
        public E removeLast() {
        
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
    
        // 添加头部元素
        public void addFirst(E e) {
        
            linkFirst(e);
        }
    
        // 添加头部元素的具体执行方法
        private void linkFirst(E e) {
        
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
    
        // 添加尾部元素
        public void addLast(E e) {
        
            linkLast(e);
        }
    
        // 添加尾部元素的具体方法
        void linkLast(E e) {
        
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    
        // 查询链表个数
        public int size() {
        
            return size;
        }
    
        // 清空链表
        public void clear() {
        
            for (Node<E> x = first; x != null; ) {
        
                Node<E> next = x.next;
                x.item = null;
                x.next = null;
                x.prev = null;
                x = next;
            }
            first = last = null;
            size = 0;
            modCount++;
        }
    
        // 根据下标获取元素
        public E get(int index) {
        
            checkElementIndex(index);
            return node(index).item;
        }
    
        private static class Node<E> {
        
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
        
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }
        // 忽略其他方法......
    }

双向链表最新实现

public class Node {
        
        private int node;
        private String name;
        private Node next;
        private Node pre;
    
        public Node(int node, String name) {
        
            this.node = node;
            this.name = name;
        }
    
        public int getNode() {
        
            return node;
        }
    
        public String getName() {
        
            return name;
        }
    
        public Node getNext() {
        
            return next;
        }
    
        public Node getPre() {
        
            return pre;
        }
    
        public void setNode(int node) {
        
            this.node = node;
        }
    
        public void setName(String name) {
        
            this.name = name;
        }
    
        public void setNext(Node next) {
        
            this.next = next;
        }
    
        public void setPre(Node pre) {
        
            this.pre = pre;
        }
    
        @Override
        public String toString() {
        
            return "Node{" +
                    "node=" + node +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

增删改查

public class DoubleLinkedLIST {
        
        private Node head = new Node(0,"");
        
        //获取链表头
        public Node getHead() {
        
            return head;
        }
        
        //头部添加
        public void addFirst(Node node){
        
            Node temp = head;
    
            if(temp == null){
        
                head.setNext(node);
            }else{
        
                node.setNext(temp.getNext());
                node.setPre(temp.getNext());
                head.setNext(node);
            }
        }
        //尾部添加
        public void addLast(Node node){
        
            Node temp = head;
    
            while(true){
        
                if(temp.getNext() == null){
        //说明已找到链表尾部
                    break;
                }if(temp.getNode() == node.getNode()){
        
                    System.out.println(node.getNode() + "已存在，添加失败");
                    break;
                }
                temp = temp.getNext();
            }
            temp.setNext(node);
            node.setPre(temp);
        }
        //根据编号插入
        public void addOderBy(Node node) {
        
           Node temp = head;
            boolean flag = false; // 标志添加的编号是否存在
            while(true) {
        
                if (temp.getNext() == null) {
         // 说明temp已经在链表的最后
                    break;
                }
                if (temp.getNext().getNode() > node.getNode()) {
         // 位置找到，就在temp的后面插入
                    break;
                } else if (temp.getNext().getNode() == node.getNode()) {
         // 说明编号已经存在
                    flag = true;
                    break;
                }
                temp = temp.getNext(); // 后移，遍历当前链表
            }
            // 判断flag的值
            if (flag == true) {
         // 不能添加，说明编号存在
                System.out.println("准备插入的英雄的编号 "+node.getNode()+" 已经存在，不能加入");
            } else {
        
                // 插入到链表中，temp的后面
                node.setNext(temp.getNext());
                if (temp.getNext() != null) {
        
                    temp.getNext().setPre(node);
                }
                temp.setNext(node);
                node.setPre(temp);
            }
    
        }
        //删除第k个元素
        public void delete(int k){
        
            if (head.getNext() == null) {
        //判断链表是否为空
                System.out.println("链表为空无法删除");
                return;
            }
    
            Node temp = head.getNext(); // 辅助变量（指针）
            boolean flag = false; // 标志是否找到待删除节点
            while(true) {
        
                if (temp == null) {
         // 已经到链表的最后
                    break;
                }
                if (temp.getNode() == k) {
        
                    // 找到了待删除节点
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            
            if (flag) {
         // 找到
                // 可以删除
                temp.getPre().setNext(temp.getNext());
                if (temp.getNext() != null) {
        
                    temp.getNext().setPre(temp.getPre());
                }
            } else {
        
                System.out.println("要删除的 " + k + " 节点不存在");
            }
        }
        
        //更新数据
        public void upPata(Node node){
        
            // 判断是否为空
            if (head.getNext() == null) {
        
                System.out.println("链表为空");
                return;
            }
            // 定义一个辅助变量
            Node temp = head.getNext();
            boolean flag = false; // 表示是否找到该节点,默认为false
            while (true) {
        
                if (temp == null) {
        
                    break;
                }
                if (temp.getNode() == node.getNode()) {
        
                    // 找到
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            // 根据flag判断是否找到要修改的节点
            if (flag) {
        
                temp.setName(node.getName());
            } else {
        
                System.out.println("没有找到编号为 " + node.getNode() + " 的节点");
            }
        }
    
        //显示节点
        public void show(Node head){
        
            Node temp = head.getNext();
    
            while(temp != null){
        
                System.out.println(temp);
                temp = temp.getNext();
            }
        }
    }

#### 2.1.3 单向循环链表 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EGJaCFb5-1622707219324)(C:\\Users\\HuFeiHu\\AppData\\Roaming\\Typora\\typora-user-images\\image-20201111133024358.png)\]

public class CiNode {
        
        private Object data;
        private CiNode next;
        private static CiNode first; // 临时结点，头结点，并不是链表里想要的值，起到标记链表头的作用
    
        public CiNode() {
        
            super();
        }
    
        public CiNode(Object data, CiNode next) {
        
            super();
            this.data = data;
            this.next = next;
        }
    
        public Object getData() {
        
            return data;
        }
    
        public void setData(Object data) {
        
            this.data = data;
        }
    
        public CiNode getNext() {
        
            return next;
        }
    
        public void setNext(CiNode next) {
        
            this.next = next;
        }
    
        public static void add(CiNode node, int index) {
        
            if (index == 0) {
        
                node.next = first.next;
                first.next = node;
            } else {
        
                int temp = 0;
                for (CiNode n = first.next;; n = n.next) {
        
                    temp++;
                    if (temp == index) {
        
                        node.next = n.next;
                        n.next = node;
                        break;
                    }
                }
            }
        }
    
        public static void remove(int index) {
        
            if (index % 5 == 0) {
         // 删除第一个元素，考虑循环
                first.next = first.next.next;
            } else {
        
                int temp = 0;
                for (CiNode n = first.next;; n = n.next) {
        
                    if (n == first) {
        
                        temp -= 1; // 减一是因为链表循环计数时会把first记一次，所以这里减一次，使下标一致
                    }
                    temp++;
                    if (temp == index) {
        
                        n.next = n.next.next;
                        break;
                    }
                }
            }
        }
    
        public static void display() {
        
            for (CiNode n = first.next; n != first; n = n.next) {
        
                System.out.print(n.data + " ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
        
            CiNode node4 = new CiNode("ddd", null);
            CiNode node3 = new CiNode("ccc", node4);
            CiNode node2 = new CiNode("bbb", node3);
            CiNode node1 = new CiNode("aaa", node2);
            first = new CiNode(null, node1);
            node4.next = first;
            System.out.println("当前链表：");
            display();
            add(new CiNode("eee", null), 5); // 传5进去是为了体现循环，当参数大于了链表长度时，又回到first
            System.out.println("插入后链表：");
            display();
            remove(11);
            System.out.println("删除后链表：");
            display();
        }
    }

#### 2.1.4 双向循环链表 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PCktarMG-1622707219325)(C:\\Users\\HuFeiHu\\AppData\\Roaming\\Typora\\typora-user-images\\image-20201111133226060.png)\]

public class CiDlNode {
        
        private Object data;
        private CiDlNode next;
        private CiDlNode prev;
        private static CiDlNode first;
    
        public CiDlNode() {
        
            super();
        }
    
        public CiDlNode(Object data, CiDlNode next, CiDlNode prev) {
        
            super();
            this.data = data;
            this.next = next;
            this.prev = prev;
        }
    
        public static void insert(Object data, int index) {
        
            CiDlNode node = new CiDlNode(data, null, null);
            if (index == 0) {
        
                node.next = first.next;
                first.next.prev = node;
                first.next = node;
                node.prev = first;
    
            } else {
        
                int temp = 0;
                for (CiDlNode n = first.next;; n = n.next) {
        
                    temp++;
                    if (temp == index) {
        
                        node.next = n.next;
                        node.next = n.next;
                        n.next.prev = node;
                        n.next = node;
                        node.prev = n;
                        break;
                    }
                }
            }
        }
    
        public static void remove(Object data) {
        
            for (CiDlNode n = first.next; n != first; n = n.next) {
        
                if (n.data.equals(data)) {
        
                    n.prev.next = n.next;
                    n.next.prev = n;
                }
            }
        }
    
        public static void print() {
        
            for (CiDlNode node = first.next; node != first; node = node.next) {
        
                System.out.print(node.data + " ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
        
            first = new CiDlNode("0", null, null);
            CiDlNode node1 = new CiDlNode("aaa", null, first);
            CiDlNode node2 = new CiDlNode("bbb", null, node1);
            CiDlNode node3 = new CiDlNode("ccc", null, node2);
            CiDlNode node4 = new CiDlNode("ddd", first, node3);
            node3.next = node4;
            node2.next = node3;
            node1.next = node2;
            first.next = node1;
            System.out.println("当前链表:");
            print();
            insert("ddd", 5);
            System.out.println("插入后链表：");
            print();
            remove("ddd");
            System.out.println("删除后链表：");
            print();
        }
    }

### 2.2 链表的常见算法 ###

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class LinkedList {
        
    	/**
    	 * @Author：ZhangRui
    	 * @Purpose：For learning single LinkedList
    	 * @Date：2017/04/23
    	 * @Email：1138517609@qq.com
    	 * @Blog：http://blog.csdn.net/u011489043
    	 * @GitHub：https://github.com/selfcon
    	 */
    	public static class Node {
        
    		int value;
    		Node next;
    
    		public Node(int n) {
        
    			this.value = n;
    			this.next = null;
    		}
    	}
    
    	// 输出函数
    	public static void display(Node head) {
        
    		while (head != null) {
        
    			if (head.next == null) {
        
    				System.out.println(head.value);
    			} else {
        
    				System.out.print(head.value + " -> ");
    			}
    			head = head.next;
    		}
    	}
    
    	// 利用栈的特性实现逆序输出
    	public static void reverseByStack(Node head) {
        
    
    		Stack<Node> stack = new Stack<Node>();
    		while (head != null) {
        
    			stack.add(head);
    			head = head.next;
    		}
    		while (!stack.empty()) {
        
    			System.out.print(stack.pop().value + " -> ");
    		}
    		System.out.println();
    	}
    
    	// 利用动态数组实现逆序输出（前插法）
    	public static ArrayList<Integer> printListFromTailToHead(Node listNode) {
        
    		ArrayList<Integer> arr = new ArrayList<Integer>();
    		while (listNode != null) {
        
    			arr.add(0, listNode.value);
    			listNode = listNode.next;
    		}
    		return arr;
    	}
    
    	// 通过递归实现逆序输出
    	public static void reverseByRecursive(Node head) {
        
    		if (head == null)
    			return;
    		else
    			reverseByRecursive(head.next);
    		System.out.print(head.value + " -> ");
    	}
    
    	// 利用递归和动态数组
    	ArrayList<Integer> arrayList = new ArrayList<Integer>();
    
    	public ArrayList<Integer> printListFromTailToHead1(Node listNode) {
        
    		if (listNode != null) {
        
    			this.printListFromTailToHead1(listNode.next);
    			arrayList.add(listNode.value);
    		}
    		return arrayList;
    	}
    
    	// 获取链表的长度
    	public static int getListLength(Node head) {
        
    		int length = 0;
    		while (head != null) {
        
    			length++;
    			head = head.next;
    		}
    		return length;
    	}
    
    	// 链表反转
    	public static Node reverseList(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node pre = null;
    		Node nex = null;
    		while (head != null) {
        
    			nex = head.next;
    			head.next = pre;
    			pre = head;
    			head = nex;
    		}
    		return pre;
    	}
    
    	// 通过递归实现链表反转
    	public static Node reverseListRecursive(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node nex = reverseListRecursive(head.next);
    		head.next.next = head;
    		head.next = null;
    		return nex;
    	}
    
    	// 删除链表中某个特定节点
    	public static Node deleteOneNode(Node head, Node delNode) {
        
    		if (head == null || delNode == null)
    			return head;
    		if (delNode.next == null) {
        
    			// 尾节点
    			Node temp = head;
    			while (temp.next != null) {
        
    				if (temp.next == delNode)
    					temp.next = delNode.next;
    				temp = temp.next;
    			}
    		} else {
        
    			// 非尾节点
    			Node p = delNode.next;
    			delNode.value = p.value;
    			delNode.next = p.next;
    		}
    		return head;
    	}
    
    	// 反转链表中第m到第n个节点
    	public static Node reverseListBetween(Node head, int m, int n) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node helper = new Node(0);
    		helper.next = head;
    		Node nex = head;
    		Node pre = helper;
    		// 首先定位到第m个节点
    		for (int i = 1; i < m; i++) {
        
    			pre = nex;
    			nex = nex.next;
    		}
    		// 然后将第m到第n个节点进行反转
    		for (int i = 1; i <= n - m; i++) {
        
    			Node temp = nex.next;
    			nex.next = temp.next;
    			temp.next = pre.next;
    			pre.next = temp;
    		}
    		return helper.next;
    	}
    
    	// 查找链表中倒数第k个节点 k>=0，注意k大于链表长度的情况
    	public static Node searchKthLastNode(Node head, int k) {
        
    		if (head == null || k < 0)
    			return head;
    		if (k >= getListLength(head))
    			return null;
    		Node target = head;
    		Node temp = head;
    		for (int i = 0; i <= k; i++) {
        
    			temp = temp.next;
    		}
    		// n-k
    		while (temp != null) {
        
    			target = target.next;
    			temp = temp.next;
    		}
    		temp = null;
    		target.next = null;
    		System.out.print("target.value: " + target.value + "  ");
    		return target;
    	}
    
    	// 查找链表中中间节点
    	public static Node searchMiddleNode(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		// 一般查找问题都是两个指向头节点的指针（快慢指针）共同移动。
    		int length = getListLength(head);
    		Node fast = head;
    		Node slow = head;
    		Node temp = slow;// 如果有两个中间节点，取前一个
    		while (fast != null && fast.next != null) {
        
    			temp = slow;
    			fast = fast.next.next;
    			slow = slow.next;
    		}
    		temp.next = null;
    		slow.next = null;
    		System.out.print("temp.value = " + temp.value + " slow.value = "
    				+ slow.value);
    		if (length % 2 != 0)
    			return slow;
    		else
    			return temp;
    	}
    
    	// 查找链表中中间节点 09/05/2017 补充另一种无需求长度的方法
    	// 一开始就使快指针先走一步
    	public static Node searchMiddleNode2nd(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node pre = head;
    		Node cur = head.next;
    		while (cur != null && cur.next != null) {
        
    			pre = pre.next;
    			cur = cur.next.next;
    		}
    		System.out.print("pre = " + pre.value);
    		return pre;
    	}
    
    	// 删除倒数第n个节点
    	public static Node removeNthLastNode(Node head, int n) {
        
    		if (head == null || n < 0)
    			return head;
    		if (n > getListLength(head))
    			return null;
    		Node temp = head;
    		Node target = head;
    		while (n > 0) {
        
    			temp = temp.next;// 定位倒数第n个节点
    			n--;
    		}
    		// System.out.print("temp.value: " + temp.value + "  ");
    		// 删除第一个节点
    		if (temp == null)
    			return head.next;
    		while (temp.next != null) {
        
    			target = target.next;// 定位倒数第n+1个节点
    			temp = temp.next;
    		}
    		temp = null;
    		// System.out.print("target.value: " + target.value + "  ");
    		if (target.next != null)
    			target.next = target.next.next;
    		return head;
    	}
    
    	// 判断链表是否存在环
    	public static boolean isExistCycleList(Node head) {
        
    		/*
    		 * 时间复杂度为O(n)，空间复杂度为O(1) 当一个存在环的链表足够长，而环足够小，那么会存在快指针永远不会追上慢指针的情况。
    		 * 快慢指针只适用于环出现在链表尾部的情况，也就是单链表环的问题，而无法解决链表存在循环的问题
    		 * 设定两个指针slow,fast，其中slow每次向前移动一步（俗称慢指针），fast每次向前移动两步（快指针）。
    		 * 如果单链表存在环，则slow和fast相遇；否则fast将首先遇到null
    		 */
    		if (head == null || head.next == null)
    			return false;
    		Node fast = head;
    		Node slow = head;
    		while (fast != null && fast.next != null) {
        
    			fast = fast.next.next;
    			slow = slow.next;
    			if (slow == fast)
    				return true;
    		}
    		slow = null;
    		fast = null;
    		return false;
    	}
    
    	// 利用set的无重复性，判断链表是否存在环
    	public static boolean isExistCycleListBySet(Node head) {
        
    		if (head == null || head.next == null)
    			return false;
    		HashSet<Node> set = new HashSet<Node>();
    		while (head != null) {
        
    			if (set.contains(head))
    				return true;
    			else {
        
    				set.add(head);
    				head = head.next;
    			}
    		}
    		return false;
    	}
    
    	// 利用hashmap获得链表环的开始位置
    	public static Node getFirstNodeInCycleHashMap(Node head) {
        
    		Node target = null;
    		HashMap<Node, Boolean> map = new HashMap<Node, Boolean>();
    		while (head != null) {
        
    			if (map.containsKey(head)) {
        
    				target = head;
    				break;
    			} else {
        
    				map.put(head, true);
    				head = head.next;
    			}
    		}
    		return target;
    	}
    
    	// 利用快慢指针获得链表环的开始位置
    	public static Node getFirstNodeInCycleFSPointer(Node head) {
        
    		/*
    		 * 用快慢指针，与判断一个单链表中是否有环一样，找到快慢指针第一次相交的节点，
    		 * 此时这个节点距离环开始节点的长度和链表投距离环开始的节点的长度相等
    		 */
    		Node fast = head;
    		Node slow = head;
    		// 找到快慢指针第一次相交的节点
    		while (fast != null && fast.next != null) {
        
    			fast = fast.next.next;
    			slow = slow.next;
    			if (slow == fast)
    				break;
    		}
    		if (fast == null || fast.next == null)
    			return null;
    		// slow从链表头出发,fast从第一次相遇的位置出发,再次相遇时即为环开始的地方。
    		// 证明详见我博客http://blog.csdn.net/u011489043
    		slow = head;
    		while (slow != fast) {
        
    			slow = slow.next;
    			fast = fast.next;
    		}
    		fast = null;
    		return slow;
    	}
    
    	// 判断两个链表是否相交 思路一
    	public static Node isIntersect(Node head1, Node head2) {
        
    		/*
    		 * 如果两个没有环的链表相交于某个节点，那么在这个节点之后的所有节点都是两个链表所共有的
    		 * 1）遍历链表1，记录其长度len1，遍历链表2，记录其长度len2
    		 * 2）按尾部对齐，如果两个链表的长度不相同，让长度更长的那个链表从头节点先遍历abs(len1-en2),这样两个链表指针指向对齐的位置
    		 * 3）然后两个链表齐头并进，当它们相等时，就是交集的节点 时间复杂度O(n+m)，空间复杂度O(1)
    		 */
    		Node target = null;
    		if (head1 == null || head2 == null)
    			return target;
    		int lenNode1 = getListLength(head1);
    		int lenNode2 = getListLength(head2);
    		if (lenNode1 >= lenNode2) {
        
    			for (int i = 0; i < lenNode1 - lenNode2; i++)
    				head1 = head1.next;
    		} else {
        
    			for (int i = 0; i < lenNode2 - lenNode1; i++)
    				head2 = head2.next;
    		}
    		while (head1 != null && head2 != null) {
        
    			if (head1 == head2) {
        
    				target = head1;
    				break;
    			} else {
        
    				head1 = head1.next;
    				head2 = head2.next;
    			}
    		}
    		return target;
    	}
    
    	// 判断两个链表是否相交 思路二
    	public static Node isIntersect2(Node head1, Node head2) {
        
    		/*
    		 * 假定List1长度:a+n，List2 长度:b+n,且a<b(同理a>=b)
    		 * 那么p1会先到链表尾部,这时p2走到a+n位置,将p1换成List2头部 接着p2再走b+n-(n+a)=b-a
    		 * 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。
    		 * 将p2换成List1头部，p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。
    		 * 或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环 时间复杂度O(n+a+b)
    		 */
    		Node p1 = head1;
    		Node p2 = head2;
    		while (p1 != p2) {
        
    			p1 = (p1 == null) ? head2 : p1.next;
    			p2 = (p2 == null) ? head1 : p2.next;
    			// 上面两行代码是下面几句的精简版
    			// if (p1 != null) p1 = p1.next;
    			// if (p2 != null) p2 = p2.next;
    			// if (p1 != p2) {
        
    			// if (p1 == null) p1 = head2;
    			// if (p2 == null) p2 = head1;
    			// }
    		}
    		return p1;
    	}
    
    	// 利用递归合并两个有序链表
    	public static Node mergeTwoListRecursive(Node head1, Node head2) {
        
    		if (head1 == null)
    			return head2;
    		if (head2 == null)
    			return head1;
    		Node head;
    		if (head1.value < head2.value) {
        
    			head = head1;
    			head1.next = mergeTwoListRecursive(head1.next, head2);
    		} else {
        
    			head = head2;
    			head2.next = mergeTwoListRecursive(head1, head2.next);
    		}
    		return head;
    	}
    
    	// 合并两个有序链表
    	public static Node mergeTwoList(Node head1, Node head2) {
        
    		if (head1 == null)
    			return head2;
    		if (head2 == null)
    			return head1;
    		Node head = new Node(0);
    		Node temp = head;
    		while (head1 != null && head2 != null) {
        
    			if (head1.value < head2.value) {
        
    				temp.next = head1;
    				head1 = head1.next;
    			} else {
        
    				temp.next = head2;
    				head2 = head2.next;
    			}
    			temp = temp.next;
    		}
    		if (head1 != null)
    			temp.next = head1;
    		if (head2 != null)
    			temp.next = head2;
    		return head.next;
    	}
    
    	// 合并k个有序链表
    	public Node mergeKLists(ArrayList<Node> lists) {
        
    		if (lists == null || lists.size() == 0)
    			return null;
    
    		Node list_head = lists.get(0);
    		for (int i = 1; i < lists.size(); i++) {
        
    			list_head = mergeTwoList(list_head, lists.get(i));
    		}
    		return list_head;
    	}
    
    	// 链表排序之 归并排序
    	public static Node mergeSortList(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node slow = head;
    		Node fast = head.next;
    		while (fast != null && fast.next != null) {
        
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		Node right = mergeSortList(slow.next);
    		slow.next = null;
    		Node left = mergeSortList(head);
    		// /待左右两边各自有序，进行归并即可
    		Node temp_head = new Node(0);
    		Node temp_node = temp_head;
    		while (left != null && right != null) {
        
    			if (left.value < right.value) {
        
    				temp_node.next = left;
    				left = left.next;
    			} else {
        
    				temp_node.next = right;
    				right = right.next;
    			}
    			temp_node = temp_node.next;
    		}
    		if (left != null)
    			temp_node.next = left;
    		if (right != null)
    			temp_node.next = right;
    		return temp_head.next;
    	}
    
    	// 链表排序之 插入排序
    	public static Node insertSortList(Node head) {
        
    		if (head == null)
    			return null;
    		Node helper = new Node(0);// 辅助指针，防止头指针发生变化
    		Node pre = helper;
    		Node cur = head;
    		while (cur != null) {
        
    			Node next = cur.next;
    			pre = helper;
    			while (pre.next != null && pre.next.value <= cur.value) {
        
    				pre = pre.next;
    			}
    			cur.next = pre.next;
    			pre.next = cur;
    			cur = next;
    		}
    		return helper.next;
    	}
    
    	// 删除链表里的重复元素，只保留一个
    	public static Node removeDuplicateList(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node pre = head;
    		while (head != null && head.next != null) {
        
    			if (head.value == head.next.value) {
        
    				head.next = head.next.next;
    			} else {
        
    				head = head.next;
    			}
    		}
    		return pre;
    	}
    
    	// 删除链表里的重复元素，一个不留（思路一）
    	public static Node removeDuplicateListAll(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node pre = new Node(0);
    		pre.next = head;
    		Node fir = pre;// fir保存的是当前节点的前一个节点
    		Node sec = head;
    		while (sec != null) {
        
    			int value = sec.value;
    			int count_repeat = 0;
    			while (sec != null && value == sec.value) {
        
    				sec = sec.next;
    				count_repeat++;// 统计每个节点重复次数
    			}
    			if (count_repeat > 1) {
        // 若出现次数大于1，说明该节点对应的值需要删掉
    				fir.next = sec;
    			} else {
        
    				fir = fir.next;
    			}
    			if (fir != null) {
        
    				sec = fir.next;
    			}
    		}
    		return pre.next;
    	}
    
    	// 删除链表里的重复元素，一个不留（思路二：递归）
    	public static Node deleteDuplication(Node pHead) {
        
    		if (pHead == null)
    			return null;
    		if (pHead != null && pHead.next == null)
    			return pHead;
    		Node current;
    		if (pHead.next.value == pHead.value) {
        
    			current = pHead.next.next;
    			while (current != null && current.value == pHead.value)
    				current = current.next;
    			return deleteDuplication(current);
    		} else {
        
    			current = pHead.next;
    			pHead.next = deleteDuplication(current);
    			return pHead;
    		}
    	}
    
    	// 前后两两交换元素的值（递归）
    	public static Node swapPairs(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node temp = head.next;
    		head.next = swapPairs(temp.next);
    		temp.next = head;
    		return temp;
    	}
    
    	// 前后两两交换元素的值
    	public static Node swapPairsXH(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node helper = new Node(0);
    		helper.next = head;
    		Node pre = helper;
    		Node cur = head;
    		Node temp;
    		while (cur != null && cur.next != null) {
        
    			temp = cur.next;
    			cur.next = temp.next;
    			temp.next = pre.next;
    			pre.next = temp;
    			pre = cur;
    			cur = cur.next;
    		}
    		return helper.next;
    	}
    
    	// 链表分割
    	public static Node partition(Node head, int x) {
        
    		if (head == null)
    			return head;
    		Node first = new Node(0);
    		Node second = new Node(0);
    		Node temp_fir = first;
    		Node temp_sec = second;
    		while (head != null) {
        
    			if (head.value < x) {
        
    				first.next = head;
    				first = first.next;
    			} else {
        
    				second.next = head;
    				second = second.next;
    			}
    			head = head.next;
    		}
    		second.next = null;// 如果链表最后一个元素小于x，则second.next不为null
    		first.next = temp_sec.next;
    		return temp_fir.next;
    	}
    
    	// 将链表右边数n个结点移动到最左边
    	public static Node rotateRight(Node head, int n) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node target = head;
    		int len = 1;
    		while (target.next != null) {
        
    			len++;
    			target = target.next;
    		}
    		// System.out.println("len：" + len + " target: " + target);
    		target.next = head;// 首尾相连构成环
    		for (int i = 1; i < len - n % len; i++) {
        
    			head = head.next;// 走到需要断开位置的前一位置
    		}
    		target = head.next;
    		head.next = null;
    		return target;
    	}
    
    	// 每k个结点一组进行反转
    	public static Node reverseKGroup(Node head, int k) {
        
    		if (head == null || head.next == null)
    			return head;
    		Node helper = new Node(0);
    		helper.next = head;
    		Node pre = helper;
    		Node cur = head;
    		int count = 0;
    		while (cur != null) {
        
    			Node nex = cur.next;
    			count++;
    			if (count == k) {
        
    				count = 0;
    				pre = reverse(pre, nex);
    			}
    			cur = nex;
    		}
    		return helper.next;
    	}
    
    	public static Node reverse(Node start, Node end) {
        
    		if (start == null || start.next == null)
    			return start;
    		Node pre = start.next;
    		Node nex = start.next.next;
    		while (nex != end) {
        
    			Node temp_nex = nex.next;
    			nex.next = start.next;
    			start.next = nex;
    			nex = temp_nex;
    		}
    		pre.next = end;
    		return pre;
    	}
    	//
    
    	// Given a singly linked list L: L0→L1→…→Ln-1→Ln,
    	// reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
    	public static Node reorderList(Node head) {
        
    		if (head == null || head.next == null)
    			return head;
    		// 首先，找到中间点，分为前后两部分
    		Node slow = head;
    		Node fast = head.next;
    		while (fast != null && fast.next != null) {
        
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		System.out.println("slow.value: " + slow.value);
    		// 其次，将后部分的链表进行逆置
    		Node second = slow.next;
    		Node pre_rever = null;
    		Node nex_rever = null;
    		while (second != null) {
        
    			nex_rever = second.next;
    			second.next = pre_rever;
    			pre_rever = second;
    			second = nex_rever;
    		}
    		// 最后对前后两部分head和second进行交叉连接
    		Node temp_second = pre_rever;
    		slow.next = null;
    		Node temp_head = head;
    		while (temp_second != null) {
        
    			Node pre = temp_second.next;
    			// System.out.println("temp.value: " + temp.value);
    			temp_second.next = temp_head.next;
    			temp_head.next = temp_second;
    			temp_second = pre;
    			temp_head = temp_head.next.next;
    		}
    		return head;
    	}
    
    	// 判断是否为回文链表 利用栈的特性
    	public static Boolean isPalindrome(Node head) {
        
    		if (head == null)
    			return false;
    		Stack<Integer> sta = new Stack<Integer>();
    		Node temp = head;
    		while (temp != null) {
        
    			sta.push(temp.value);
    			temp = temp.next;
    		}
    		while (!sta.isEmpty()) {
        
    			if (sta.pop() != head.value)
    				return false;
    			head = head.next;
    		}
    		return true;
    	}
    
    	// 判断是否为回文链表 利用栈和快慢指针的特性，减少空间开销
    	public static Boolean isPalindrome2(Node head) {
        
    		if (head == null)
    			return false;
    		Node slow = head;
    		Node fast = head;
    		Stack<Integer> sta = new Stack<Integer>();
    		while (fast != null && fast.next != null) {
        
    			sta.push(slow.value);
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		if (fast != null)// 如果有奇数个节点，slow再往后移动一个
    			slow = slow.next;
    
    		while (!sta.isEmpty()) {
        
    			if (sta.pop() != slow.value)
    				return false;
    			slow = slow.next;
    		}
    		return true;
    	}
    
    	// 判断是否为回文链表 先反转，再和之前的依次比较
    	// public static Boolean isPalindrome3(Node head){
        
    	// if(head == null)
    	// return false;
    	// Node temp = head;
    	// Node reverseHead = reverseList(temp);
    	// while(head != null){ ///head 为什么只剩一个节点了？？
    	// System.out.print(head.value + " -> ");
    	// head = head.next;
    	// }
    	// System.out.println();
    	// while(reverseHead != null){
        
    	// System.out.print(reverseHead.value + " -> ");
    	// reverseHead = reverseHead.next;
    	// }
    	// return true;
    	// }
    
    	// 判断是否为回文链表 递归的思想
    	static Node temp_pp = null;
    
    	public static Boolean isPalindrome4(Node head) {
        
    		if (head == null)
    			return true;
    		if (temp_pp == null)
    			temp_pp = head;
    		if (isPalindrome4(head.next) && (temp_pp.value == head.value)) {
        
    			temp_pp = temp_pp.next;
    			return true;
    		}
    		temp_pp = null;
    		return false;
    	}
    
    	public static void main(String[] args) {
        
    		/*
    		 * 主函数： （注）上面有很多函数体并未在下面调用大家可按需查找，调用测试。 如果有疑问或者建议，欢迎交流。
    		 */
    		Scanner scan = new Scanner(System.in);
    		Node head = null;// 测试链表一
    		// Node head_second = null;//测试链表二
    		int i = 0;
    		// int j= 0;
    		System.out.println("请依次输入链表1的元素：");
    		// 输入头节点
    		if (scan.hasNextInt()) {
        
    			head = new Node(scan.nextInt());
    		}
    		// 输入其他链表元素
    		Node temp = head;
    		while (scan.hasNext()) {
        
    			temp.next = new Node(scan.nextInt());
    			temp = temp.next;
    			i++;
    			if (i == 5)// 决定链表元素的个数
    				break;
    		}
    		// System.out.println("请依次待删除节点：");
    		// Node delNode = new Node(scan.nextInt());
    
    		// System.out.println("请依次输入链表2的元素：");
    		// 输入头节点
    		// if(scan.hasNextInt()){
        
    		// head_second = new Node(scan.nextInt());
    		// }
    		// 输入其他链表元素
    		// Node temp_second = head_second;
    		// while(scan.hasNext()){
        
    		// temp_second.next = new Node(scan.nextInt());
    		// temp_second = temp_second.next;
    		// j++;
    		// if(j == 4)//决定链表元素的个数
    		// break;
    		// }
    
    		// System.out.print("输入两个整数： ");
    		int m = scan.nextInt();
    		// int n = scan.nextInt();
    		scan.close();
    
    		// case 1
    		System.out.print("链表元素： ");
    		display(head);
    
    		// System.out.print("输出中间节点： " + searchMiddleNode2nd(head));
    		// Node dell = removeNthFromEnd(head, n);
    		// display(dell);
    
    		// Node del = reverseBetween(head, m, n);
    		// display(del);
    
    		// case 2
    		// System.out.print("前后交叉排列后： ");
    		// Node reorderNode = reorderList(head);
    		// display(reorderNode);
    
    		// case 3
    		// System.out.println("链表长度： " + getListLength(head) + " 是否为有环链表：" +
    		// cycleList(head));
    
    		// case 4
    		// System.out.print("两两交换位置后： ");
    		// Node swapNode = swap(head);
    		// Node swapNodeXH = swapPairsXH(head);
    		// display(swapNode);
    
    		// case 5
    		// System.out.print("根据与x的大小重新分组后： ");
    		// Node partition = partitionT(head, m);
    		// display(partition);
    
    		// case 6
    		// System.out.print("删除全部重复元素后： ");
    		// Node removeDuplicateAll = removeDuplicateListAll(head);
    		// Node removeDuplicateAllDG = deleteDuplication(head);
    		// display(removeDuplicateAllDG);
    
    		// case 7
    		// System.out.print("删除重复元素后： ");
    		// Node removeDuplicate = removeDuplicateList(head);
    		// display(removeDuplicate);
    
    		// case 8
    		// System.out.print("翻转第m到第n个值： ");
    		// Node reverseBetween = reverseListBetween(head, m, n);
    		// display(reverseBetween);
    
    		// case 9
    		// System.out.print("循环合并： ");
    		// Node mergeSorted = mergeTwoList(head, head_second);
    		// display(mergeSorted);
    
    		// case 10
    		// System.out.print("递归合并： ");
    		// Node DGmergeSorted = mergeTwoListRecursive(head, head_second);
    		// display(DGmergeSorted);
    
    		// case 11
    		Node target = reverseKGroup(head, m);
    		System.out.print("reorder：  ");
    		display(target);
    
    		// case 12
    		// Node sortHead = insertSortList(head);
    		// System.out.print("将链表插入排序后输出： ");
    		// display(sortHead);
    
    		// case 13
    		// System.out.print("归并排序后输出： ");
    		// Node mergeSortNode = mergeSortList(head);
    		// display(mergeSortNode);
    
    		// case 14
    		// System.out.print("通过栈的先入后出特性实现链表逆序输出： ");
    		// reverseByStack(head);
    
    		// case 15
    		// System.out.print("通过递归实现链表逆序输出： ");
    		// reverseByRecursive(head);
    		// System.out.println();
    
    		// case 16
    		// System.out.print("通过调整指针实现链表反转：： ");
    		// Node reHead = reverseList(head);
    		// display(reHead);
    
    		// case 17
    		// System.out.print("通过递归实现链表反转：： ");
    		// Node reHead = reverseListRecursive(head);
    		// display(reHead);
    
    		// case 18
    		// System.out.print("输出中间节点后的链表元素： ");
    		// Node midHead = searchKthLastNode(head, m);
    		// display(midHead);
    
    		// case 19
    		// System.out.print("通过动态数组实现链表逆序输出： ");
    		// printListFromTailToHead(head);
    		// System.out.println();
    
    		// case 20
    		// System.out.println("栈：是回文链表吗？：  " + isPalindrome(head));
    		// System.out.println("栈和快慢指针：是回文链表吗？：  " + isPalindrome2(head));
    		// //System.out.println("是回文链表吗？：  " + isPalindrome3(head));
    		// System.out.println("递归思路：是回文链表吗？：  " + isPalindrome4(head));
    	}
    }

### 2.3 经典题目 ###

#### [反转链表][Link 1] ####

方法一：利用栈数据结构

public ListNode reverseList(ListNode head) {
        
        if (head == null) return null;
        Stack<ListNode> stack = new Stack<>();
        stack.push(head); // 存入第一个节点
        while (head.next != null) {
        
            stack.push(head.next); // 存入其他节点
            head = head.next; // 指针移动的下一位
        }
        // 反转链表
        ListNode listNode = stack.pop(); // 反转第一个元素
        ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
        while (!stack.isEmpty()) {
        
            ListNode item = stack.pop(); // 当前节点
            lastNode.next = item;
            lastNode = item;
        }
        lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
        return listNode;
    }

方法二：递归

public static ListNode reverseList(ListNode head) {
        
        if (head == null || head.next == null) {
        
            return head;
        }
        // 从下一个节点开始递归
        ListNode reverse = reverseList(head.next);
        head.next.next = head; // 设置下一个节点的 next 为当前节点
        head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
        return reverse;
    }
    
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            return recur(head, null);    // 调用递归并返回
        }
        private ListNode recur(ListNode cur, ListNode pre) {
        
            if (cur == null) return pre; // 终止条件
            ListNode res = recur(cur.next, cur);  // 递归后继节点
            cur.next = pre;              // 修改节点引用指向
            return res;                  // 返回反转链表的头节点
        }
    }

方法三：循环

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            // 最终排序的倒序链表
            ListNode prev = null;
            while (head != null) {
        
                // 循环的下个节点
                ListNode next = head.next;
                // 反转节点操作
                head.next = prev;
                // 存储下个节点的上个节点
                prev = head;
                // 移动指针到下一个循环
                head = next;
            }
            return prev;
        }
    }

#### [K 个一组翻转链表][K] ####

class Solution {
        
        public ListNode reverseKGroup(ListNode head, int k) {
        
            ListNode hair = new ListNode(0);
            hair.next = head;
            ListNode pre = hair;
    
            while (head != null) {
        
                ListNode tail = pre;
                // 查看剩余部分长度是否大于等于 k
                for (int i = 0; i < k; ++i) {
        
                    tail = tail.next;
                    if (tail == null) {
        
                        return hair.next;
                    }
                }
                ListNode nex = tail.next;
                ListNode[] reverse = myReverse(head, tail);
                head = reverse[0];
                tail = reverse[1];
                // 把子链表重新接回原链表
                pre.next = head;
                tail.next = nex;
                pre = tail;
                head = tail.next;
            }
    
            return hair.next;
        }
    
        public ListNode[] myReverse(ListNode head, ListNode tail) {
        
            ListNode prev = tail.next;
            ListNode p = head;
            while (prev != tail) {
        
                ListNode nex = p.next;
                p.next = prev;
                prev = p;
                p = nex;
            }
            return new ListNode[]{
        tail, head};
        }
    }

#### [ 反转从位置 *m* 到 *n* 的链表][_ _m_ _ _n_] ####

方法一: 递归

class Solution {
        
        // Object level variables since we need the changes
        // to persist across recursive calls and Java is pass by value.
        private boolean stop;
        private ListNode left;
        public void recurseAndReverse(ListNode right, int m, int n) {
        
            // base case. Don't proceed any further
            if (n == 1) {
        
                return;
            }
            // Keep moving the right pointer one step forward until (n == 1)
            right = right.next;
            // Keep moving left pointer to the right until we reach the proper node
            // from where the reversal is to start.
            if (m > 1) {
        
                this.left = this.left.next;
            }
            // Recurse with m and n reduced.
            this.recurseAndReverse(right, m - 1, n - 1);
            // In case both the pointers cross each other or become equal, we
            // stop i.e. don't swap data any further. We are done reversing at this
            // point.
            if (this.left == right || right.next == this.left) {
        
                this.stop = true;            
            }
            // Until the boolean stop is false, swap data between the two pointers
            if (!this.stop) {
        
                int t = this.left.val;
                this.left.val = right.val;
                right.val = t;
                // Move left one step to the right.
                // The right pointer moves one step back via backtracking.
                this.left = this.left.next;
            }
        }
    
        public ListNode reverseBetween(ListNode head, int m, int n) {
        
            this.left = head;
            this.stop = false;
            this.recurseAndReverse(head, m, n);
            return head;
        }
    }

方法二: 迭代链接反转

class Solution {
        
        public ListNode reverseBetween(ListNode head, int m, int n) {
        
            // Empty list
            if (head == null) {
        
                return null;
            }
            // Move the two pointers until they reach the proper starting point
            // in the list.
            ListNode cur = head, prev = null;
            while (m > 1) {
        
                prev = cur;
                cur = cur.next;
                m--;
                n--;
            }
            // The two pointers that will fix the final connections.
            ListNode con = prev, tail = cur;
            // Iteratively reverse the nodes until n becomes 0.
            ListNode third = null;
            while (n > 0) {
        
                third = cur.next;
                cur.next = prev;
                prev = cur;
                cur = third;
                n--;
            }
            // Adjust the final connections as explained in the algorithm
            if (con != null) {
        
                con.next = prev;
            } else {
        
                head = prev;
            }
            tail.next = cur;
            return head;
        }
    }

方法三：

ListNode reverseN2M(ListNode head,int m,int n){
        
            if(m>=n||head == null){
        
                return head;
            }
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            head = dummy;
            for(int i = 1;i<m;i++){
        
                if(head == null){
        
                    return null;
                }
                head = head.next;
            }
            ListNode pmNode = head;
            ListNode mNode = head.next;
            ListNode nNode = mNode;
            ListNode pnNode = mNode.next;
            for(int i = m;i<n;i++){
        
                if(pnNode == null){
        
                    return null;
                }
                ListNode tmp = pnNode.next;
                pnNode.next = nNode;
                nNode = pnNode;
                pnNode = tmp;
            }
            pmNode.next = nNode;
            mNode.next = pnNode;
            return dummy.next;
        }

#### [环形链表][Link 2] ####

方法一：哈希表

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            Set<ListNode> seen = new HashSet<ListNode>();
            while (head != null) {
        
                if (!seen.add(head)) {
        
                    return true;
                }
                head = head.next;
            }
            return false;
        }
    }

方法二：快慢指针

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

**返回链表开始入环的第一个节点**

方法一：哈希表

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode pos = head;
            Set<ListNode> visited = new HashSet<ListNode>();
            while (pos != null) {
        
                if (visited.contains(pos)) {
        
                    return pos;
                } else {
        
                    visited.add(pos);
                }
                pos = pos.next;
            }
            return null;
        }
    }

方法二：快慢指针

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            ListNode slow = head, fast = head;
            while (fast != null) {
        
                slow = slow.next;
                if (fast.next != null) {
        
                    fast = fast.next.next;
                } else {
        
                    return null;
                }
                if (fast == slow) {
        
                    ListNode ptr = head;
                    while (ptr != slow) {
        
                        ptr = ptr.next;
                        slow = slow.next;
                    }
                    return ptr;
                }
            }
            return null;
        }
    }

#### [ 返回倒数第 k 个节点][_ k] ####

方法一：双指针求解

public int kthToLast(ListNode head, int k) {
        
            ListNode first = head;
            ListNode second = head;
            //第一个指针先走k步
            while (k-- > 0) {
        
                first = first.next;
            }
            //然后两个指针在同时前进
            while (first != null) {
        
                first = first.next;
                second = second.next;
            }
            return second.val;
        }

方法二：使用栈解决

public int kthToLast(ListNode head, int k) {
        
            Stack<ListNode> stack = new Stack<>();
            //链表节点压栈
            while (head != null) {
        
                stack.push(head);
                head = head.next;
            }
            //在出栈串成新的链表
            ListNode firstNode = stack.pop();
            while (--k > 0) {
        
                ListNode temp = stack.pop();
                temp.next = firstNode;
                firstNode = temp;
            }
            return firstNode.val;
        }

方法三：递归求解

//全局变量，记录递归往回走的时候访问的结点数量
        int size;
    
        public int kthToLast(ListNode head, int k) {
        
            //边界条件判断
            if (head == null)
                return 0;
            int val = kthToLast(head.next, k);
            ++size;
            //从后面数结点数小于k，返回空
            if (size < k) {
        
                return 0;
            } else if (size == k) {
        
                //从后面数访问结点等于k，直接返回传递的结点k即可
                return head.val;
            } else {
        
                //从后面数访问的结点大于k，说明我们已经找到了，
                //直接返回node即可
                return val;
            }
        }

#### [ 链表中倒数第k个节点][_k] ####

class Solution {
        
        public ListNode getKthFromEnd(ListNode head, int k) {
        
            ListNode former = head, latter = head;
            for(int i = 0; i < k; i++)
                former = former.next;
            while(former != null) {
        
                former = former.next;
                latter = latter.next;
            }
            return latter;
        }
    }

#### [旋转链表][Link 3] ####

class Solution {
        
      public ListNode rotateRight(ListNode head, int k) {
        
        // base cases
        if (head == null) return null;
        if (head.next == null) return head;
    
        // close the linked list into the ring
        ListNode old_tail = head;
        int n;
        for(n = 1; old_tail.next != null; n++)
          old_tail = old_tail.next;
        old_tail.next = head;
    
        // find new tail : (n - k % n - 1)th node
        // and new head : (n - k % n)th node
        ListNode new_tail = head;
        for (int i = 0; i < n - k % n - 1; i++)
          new_tail = new_tail.next;
        ListNode new_head = new_tail.next;
    
        // break the ring
        new_tail.next = null;
    
        return new_head;
      }
    }

#### [删除中间节点][Link 4] ####

class Solution {
        
        public void deleteNode(ListNode node) {
        
            ListNode prev = new ListNode(0);
            prev.next = node;
            node.val  = node.next.val;
            node.next = node.next.next;
        }
    }

#### [合并两个有序链表][Link 5] ####

方法一：递归

class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            if (l1 == null) {
        
                return l2;
            } else if (l2 == null) {
        
                return l1;
            } else if (l1.val < l2.val) {
        
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
        
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
    
        }
    }

方法二：迭代

class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            ListNode prehead = new ListNode(-1);
    
            ListNode prev = prehead;
            while (l1 != null && l2 != null) {
        
                if (l1.val <= l2.val) {
        
                    prev.next = l1;
                    l1 = l1.next;
                } else {
        
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
    
            // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
            prev.next = l1 == null ? l2 : l1;
    
            return prehead.next;
        }
    }

#### [两两交换链表中的节点][Link 6] ####

方法一：递归

class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode newHead = head.next;
            head.next = swapPairs(newHead.next);
            newHead.next = head;
            return newHead;
        }
    }

方法二：迭代

class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
            ListNode temp = dummyHead;
            while (temp.next != null && temp.next.next != null) {
        
                ListNode node1 = temp.next;
                ListNode node2 = temp.next.next;
                temp.next = node2;
                node1.next = node2.next;
                node2.next = node1;
                temp = node1;
            }
            return dummyHead.next;
        }
    }

#### [重排链表][Link 7] ####

方法一：线性表

class Solution {
        
        public void reorderList(ListNode head) {
        
            if (head == null) {
        
                return;
            }
            List<ListNode> list = new ArrayList<ListNode>();
            ListNode node = head;
            while (node != null) {
        
                list.add(node);
                node = node.next;
            }
            int i = 0, j = list.size() - 1;
            while (i < j) {
        
                list.get(i).next = list.get(j);
                i++;
                if (i == j) {
        
                    break;
                }
                list.get(j).next = list.get(i);
                j--;
            }
            list.get(i).next = null;
        }
    }

方法二：寻找链表中点 + 链表逆序 + 合并链表

class Solution {
        
        public void reorderList(ListNode head) {
        
            if (head == null) {
        
                return;
            }
            ListNode mid = middleNode(head);
            ListNode l1 = head;
            ListNode l2 = mid.next;
            mid.next = null;
            l2 = reverseList(l2);
            mergeList(l1, l2);
        }
    
        public ListNode middleNode(ListNode head) {
        
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    
        public ListNode reverseList(ListNode head) {
        
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
        
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    
        public void mergeList(ListNode l1, ListNode l2) {
        
            ListNode l1_tmp;
            ListNode l2_tmp;
            while (l1 != null && l2 != null) {
        
                l1_tmp = l1.next;
                l2_tmp = l2.next;
    
                l1.next = l2;
                l1 = l1_tmp;
    
                l2.next = l1;
                l2 = l2_tmp;
            }
        }
    }

方法三：

ListNode reOrder(ListNode head){
        
            if(head == null||head.next == null){
        
                return;
            }
            ListNode mid = middleNode(head);
            ListNode tail = reverse(mid.next);
            mergeIndex(head, tail);
        }
        private void mergeIndex(ListNode head1,ListNode head2){
        
            int index = 0;
            ListNode dummy = new ListNode(0);
            while (head1!=null&&head2!=null) {
        
                if(index%2==0){
        
                    dummy.next = head1;
                    head1 = head1.next;
                }else{
        
                    dummy.next = head2;
                    head2 = head2.next;
                }
                dummy = dummy.next;
                index ++;
            }
            if(head1!=null){
        
                dummy.next = head1;
            }else{
        
                dummy.next = head2;
            }
        }

#### [回文链表][Link 8] ####

方法一：将值复制到数组中后用双指针法

class Solution {
        
        public boolean isPalindrome(ListNode head) {
        
            List<Integer> vals = new ArrayList<Integer>();
    
            // 将链表的值复制到数组中
            ListNode currentNode = head;
            while (currentNode != null) {
        
                vals.add(currentNode.val);
                currentNode = currentNode.next;
            }
    
            // 使用双指针判断是否回文
            int front = 0;
            int back = vals.size() - 1;
            while (front < back) {
        
                if (!vals.get(front).equals(vals.get(back))) {
        
                    return false;
                }
                front++;
                back--;
            }
            return true;
        }
    }

方法二：递归

class Solution {
        
        private ListNode frontPointer;
    
        private boolean recursivelyCheck(ListNode currentNode) {
        
            if (currentNode != null) {
        
                if (!recursivelyCheck(currentNode.next)) {
        
                    return false;
                }
                if (currentNode.val != frontPointer.val) {
        
                    return false;
                }
                frontPointer = frontPointer.next;
            }
            return true;
        }
    
        public boolean isPalindrome(ListNode head) {
        
            frontPointer = head;
            return recursivelyCheck(head);
        }
    }

方法三：快慢指针

class Solution {
        
        public boolean isPalindrome(ListNode head) {
        
            if (head == null) {
        
                return true;
            }
    
            // 找到前半部分链表的尾节点并反转后半部分链表
            ListNode firstHalfEnd = endOfFirstHalf(head);
            ListNode secondHalfStart = reverseList(firstHalfEnd.next);
    
            // 判断是否回文
            ListNode p1 = head;
            ListNode p2 = secondHalfStart;
            boolean result = true;
            while (result && p2 != null) {
        
                if (p1.val != p2.val) {
        
                    result = false;
                }
                p1 = p1.next;
                p2 = p2.next;
            }        
    
            // 还原链表并返回结果
            firstHalfEnd.next = reverseList(secondHalfStart);
            return result;
        }
    
        private ListNode reverseList(ListNode head) {
        
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
        
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    
        private ListNode endOfFirstHalf(ListNode head) {
        
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    }

#### [删除链表中的节点][Link 9] ####

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

#### [两数相加][Link 10] ####

class Solution {
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            ListNode head = null, tail = null;
            int carry = 0;
            while (l1 != null || l2 != null) {
        
                int n1 = l1 != null ? l1.val : 0;
                int n2 = l2 != null ? l2.val : 0;
                int sum = n1 + n2 + carry;
                if (head == null) {
        
                    head = tail = new ListNode(sum % 10);
                } else {
        
                    tail.next = new ListNode(sum % 10);
                    tail = tail.next;
                }
                carry = sum / 10;
                if (l1 != null) {
        
                    l1 = l1.next;
                }
                if (l2 != null) {
        
                    l2 = l2.next;
                }
            }
            if (carry > 0) {
        
                tail.next = new ListNode(carry);
            }
            return head;
        }
    }

#### [链表的中间结点][Link 11] ####

方法一：数组

class Solution {
        
        public ListNode middleNode(ListNode head) {
        
            ListNode[] A = new ListNode[100];
            int t = 0;
            while (head != null) {
        
                A[t++] = head;
                head = head.next;
            }
            return A[t / 2];
        }
    }

方法二：单指针法

class Solution {
        
        public ListNode middleNode(ListNode head) {
        
            int n = 0;
            ListNode cur = head;
            while (cur != null) {
        
                ++n;
                cur = cur.next;
            }
            int k = 0;
            cur = head;
            while (k < n / 2) {
        
                ++k;
                cur = cur.next;
            }
            return cur;
        }
    }

方法三：快慢指针法

class Solution {
        
        public ListNode middleNode(ListNode head) {
        
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

#### [合并K个升序链表][K 1] ####

方法一：顺序合并

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            ListNode ans = null;
            for (int i = 0; i < lists.length; ++i) {
        
                ans = mergeTwoLists(ans, lists[i]);
            }
            return ans;
        }
    
        public ListNode mergeTwoLists(ListNode a, ListNode b) {
        
            if (a == null || b == null) {
        
                return a != null ? a : b;
            }
            ListNode head = new ListNode(0);
            ListNode tail = head, aPtr = a, bPtr = b;
            while (aPtr != null && bPtr != null) {
        
                if (aPtr.val < bPtr.val) {
        
                    tail.next = aPtr;
                    aPtr = aPtr.next;
                } else {
        
                    tail.next = bPtr;
                    bPtr = bPtr.next;
                }
                tail = tail.next;
            }
            tail.next = (aPtr != null ? aPtr : bPtr);
            return head.next;
        }
    }

方法二：分治合并

public ListNode merge(ListNode[] lists, int l, int r) {
        
            if (l == r) {
        
                return lists[l];
            }
            if (l > r) {
        
                return null;
            }
            int mid = (l + r) >> 1;
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
    
        public ListNode mergeTwoLists(ListNode a, ListNode b) {
        
            if (a == null || b == null) {
        
                return a != null ? a : b;
            }
            ListNode head = new ListNode(0);
            ListNode tail = head, aPtr = a, bPtr = b;
            while (aPtr != null && bPtr != null) {
        
                if (aPtr.val < bPtr.val) {
        
                    tail.next = aPtr;
                    aPtr = aPtr.next;
                } else {
        
                    tail.next = bPtr;
                    bPtr = bPtr.next;
                }
                tail = tail.next;
            }
            tail.next = (aPtr != null ? aPtr : bPtr);
            return head.next;
        }
    }

方法三：使用优先队列合并

class Solution {
        
        class Status implements Comparable<Status> {
        
            int val;
            ListNode ptr;
    
            Status(int val, ListNode ptr) {
        
                this.val = val;
                this.ptr = ptr;
            }
    
            public int compareTo(Status status2) {
        
                return this.val - status2.val;
            }
        }
    
        PriorityQueue<Status> queue = new PriorityQueue<Status>();
    
        public ListNode mergeKLists(ListNode[] lists) {
        
            for (ListNode node: lists) {
        
                if (node != null) {
        
                    queue.offer(new Status(node.val, node));
                }
            }
            ListNode head = new ListNode(0);
            ListNode tail = head;
            while (!queue.isEmpty()) {
        
                Status f = queue.poll();
                tail.next = f.ptr;
                tail = tail.next;
                if (f.ptr.next != null) {
        
                    queue.offer(new Status(f.ptr.next.val, f.ptr.next));
                }
            }
            return head.next;
        }
    }

#### [奇偶链表][Link 12] ####

public class Solution {
        
        public ListNode oddEvenList(ListNode head) {
        
            if (head == null) return null;
            ListNode odd = head, even = head.next, evenHead = even;
            while (even != null && even.next != null) {
        
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = evenHead;
            return head;
        }
    }

#### [两个链表的第一个公共节点][Link 13] ####

方法一：通过集合set解决

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        //创建集合set
        Set<ListNode> set = new HashSet<>();
        //先把链表A的结点全部存放到集合set中
        while (headA != null) {
        
            set.add(headA);
            headA = headA.next;
        }
    
        //然后访问链表B的结点，判断集合中是否包含链表B的结点，如果包含就直接返回
        while (headB != null) {
        
            if (set.contains(headB))
                return headB;
            headB = headB.next;
        }
        //如果集合set不包含链表B的任何一个结点，说明他们没有交点，直接返回null
        return null;
    }

方法二：先统计两个链表的长度

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        //统计链表A和链表B的长度
        int lenA = length(headA), lenB = length(headB);
    
        //如果节点长度不一样，节点多的先走，直到他们的长度一样为止
        while (lenA != lenB) {
        
            if (lenA > lenB) {
        
                //如果链表A长，那么链表A先走
                headA = headA.next;
                lenA--;
            } else {
        
                //如果链表B长，那么链表B先走
                headB = headB.next;
                lenB--;
            }
        }
    
        //然后开始比较，如果他俩不相等就一直往下走
        while (headA != headB) {
        
            headA = headA.next;
            headB = headB.next;
        }
        //走到最后，最终会有两种可能，一种是headA为空，
        //也就是说他们俩不相交。还有一种可能就是headA
        //不为空，也就是说headA就是他们的交点
        return headA;
    }
    
    //统计链表的长度
    private int length(ListNode node) {
        
        int length = 0;
        while (node != null) {
        
            node = node.next;
            length++;
        }
        return length;
    }

方法三：双指针解决

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        //tempA和tempB我们可以认为是A,B两个指针
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
        
            //如果指针tempA不为空，tempA就往后移一步。
            //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
            tempA = tempA == null ? headB : tempA.next;
            //指针tempB同上
            tempB = tempB == null ? headA : tempB.next;
        }
        //tempA要么是空，要么是两链表的交点
        return tempA;
    }

#### [排序链表][Link 14] ####

解答一：归并排序（递归法）

class Solution {
        
        public ListNode sortList(ListNode head) {
        
            if (head == null || head.next == null)
                return head;
            ListNode fast = head.next, slow = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode tmp = slow.next;
            slow.next = null;
            ListNode left = sortList(head);
            ListNode right = sortList(tmp);
            ListNode h = new ListNode(0);
            ListNode res = h;
            while (left != null && right != null) {
        
                if (left.val < right.val) {
        
                    h.next = left;
                    left = left.next;
                } else {
        
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            h.next = left != null ? left : right;
            return res.next;
        }
    }

解答二：归并排序（从底至顶直接合并）

ListNode sortList(ListNode head){
        
            if(head == null|| head.next == null){
        
                return head;
            }
            ListNode mid = middleNode(head);
            ListNode right = sortList(mid.next);
            mid.next = null;
            ListNode left = sortList(head);
            return merge(left, right);
        }
        ListNode middleNode(ListNode head){
        
            ListNode slow = head;
            ListNode fast = head.next;
            while(fast!=null&fast.next!=null){
        
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
        ListNode merge(ListNode n1,ListNode n2){
        
            ListNode dummy = new ListNode(0);
            ListNode node = dummy;
            while (n1!=null&&n2!=null) {
        
                if(n1.val<n2.val){
        
                    node.next = n1;
                    n1 = n1.next;
                }else{
        
                    node.next = n2;
                    n2 = n2.next;
                }
                node = node.next;
            }
            if(n1!=null){
        
                node.next = n1;
            }else{
        
                node.next = n2;
            }
            return dummy.next;
        }

#### [删除链表的倒数第N个节点][N] ####

方法一：计算链表长度

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode dummy = new ListNode(0, head);
            int length = getLength(head);
            ListNode cur = dummy;
            for (int i = 1; i < length - n + 1; ++i) {
        
                cur = cur.next;
            }
            cur.next = cur.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    
        public int getLength(ListNode head) {
        
            int length = 0;
            while (head != null) {
        
                ++length;
                head = head.next;
            }
            return length;
        }
    }

方法二：栈

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode dummy = new ListNode(0, head);
            Deque<ListNode> stack = new LinkedList<ListNode>();
            ListNode cur = dummy;
            while (cur != null) {
        
                stack.push(cur);
                cur = cur.next;
            }
            for (int i = 0; i < n; ++i) {
        
                stack.pop();
            }
            ListNode prev = stack.peek();
            prev.next = prev.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    }

方法三：一次遍历

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode dummy = new ListNode(0, head);
            ListNode first = head;
            ListNode second = dummy;
            for (int i = 0; i < n; ++i) {
        
                first = first.next;
            }
            while (first != null) {
        
                first = first.next;
                second = second.next;
            }
            second.next = second.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    }

#### [移除重复节点][Link 15] ####

方法一：哈希表

class Solution {
        
        public ListNode removeDuplicateNodes(ListNode head) {
        
            if (head == null) {
        
                return head;
            }
            Set<Integer> occurred = new HashSet<Integer>();
            occurred.add(head.val);
            ListNode pos = head;
            // 枚举前驱节点
            while (pos.next != null) {
        
                // 当前待删除节点
                ListNode cur = pos.next;
                if (occurred.add(cur.val)) {
        
                    pos = pos.next;
                } else {
        
                    pos.next = pos.next.next;
                }
            }
            pos.next = null;
            return head;
        }
    }

方法二：两重循环

class Solution {
        
        public ListNode removeDuplicateNodes(ListNode head) {
        
            ListNode ob = head;
            while (ob != null) {
        
                ListNode oc = ob;
                while (oc.next != null) {
        
                    if (oc.next.val == ob.val) {
        
                        oc.next = oc.next.next;
                    } else {
        
                        oc = oc.next;
                    }
                }
                ob = ob.next;
            }
            return head;
        }
    }

[img]: /images/20221014/66f5153e0ad149479a8f405d78c7a22b.png
[Link 1]: https://leetcode-cn.com/problems/reverse-linked-list/
[K]: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
[_ _m_ _ _n_]: https://leetcode-cn.com/problems/reverse-linked-list-ii/
[Link 2]: https://leetcode-cn.com/problems/linked-list-cycle/
[_ k]: https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/
[_k]: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[Link 3]: https://leetcode-cn.com/problems/rotate-list/
[Link 4]: https://leetcode-cn.com/problems/delete-middle-node-lcci/
[Link 5]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[Link 6]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
[Link 7]: https://leetcode-cn.com/problems/reorder-list/
[Link 8]: https://leetcode-cn.com/problems/palindrome-linked-list/
[Link 9]: https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
[Link 10]: https://leetcode-cn.com/problems/add-two-numbers/
[Link 11]: https://leetcode-cn.com/problems/middle-of-the-linked-list/
[K 1]: https://leetcode-cn.com/problems/merge-k-sorted-lists/
[Link 12]: https://leetcode-cn.com/problems/odd-even-linked-list/
[Link 13]: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
[Link 14]: https://leetcode-cn.com/problems/sort-list/
[N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[Link 15]: https://leetcode-cn.com/problems/remove-duplicate-node-lcci/