我们在这篇文章主要记录下链表的基本操作. 主要包括

• 反转链表
• 检测环
• 两个有序的链表合并
• 删除倒数第K个节点
• 求链表的中间结点

首先定义单向链表, 数据包含整型的变量和下一个节点的指针.

 public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }

定义print方法,顺序打印链表的值.验证结果的正确性.

public static void print(Node list) {
        while (list != null) {
            System.out.print(list.data);
            list = list.next;
        }

        System.out.println("======================");
    }

一. 反转链表

链表前进的过程中记录下前一个节点的指针. 同时改变当前节点的指针. 使当前节点指向前一个节点.最后返回反转后的链表. 我练习的时候,犯了一个错误. 我想用同一个变量表示反转前, 反转后的链表. 但是这样是行不通的. 因为这里面list传递过来的是一个引用. 而我再list.next = prev; 这一行代码把list的内在属性改变了. 相当于list.next =null; list没有下一个节点了. list 中只有头结点的数据. 这里需要注意.

 /**
     * 反转链表
     *
     * @param list 入参链表
     * @return 反转链表
     */
    public static Node reverse(Node list) {
        Node prev = null;
        Node current = list;
        Node head = null;
        while (current != null) {
            Node next = current.next;
            current.next = prev;
            prev = current;
            if (next == null) {
                head = current;
            }
            current = next;
        }
        return head;

    }

 @Test
    public void reverseTest() {
        Node head = new Node(1, null);
        head.next = new Node(2, null);
        print(head);
        Node rNode = reverse(head);
        System.out.println("++++反转链表+++");
        print(rNode);
    }

二 . 检测环

使用快慢指针操作. 快指针一次走两步. 慢指针一次走一步. 如果存在环. 那么就会存在扣圈的情况. 终将相遇.
这里注意处理边界条件即可

   /**
     * 检测链表中是否存在环
     *
     * @param head
     * @return
     */
    private boolean checkCircle(Node head) {
        if (head == null) {
            return false;
        }

        Node fast = head;
        Node slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

 @Test
    public void checkCircleTest() {
        Node one = new Node(1, null);
        Node two = new Node(2, null);
        Node three = new Node(3, null);
        Node four = new Node(4, null);
        one.next = two;
        two.next = three;
        three.next = four;
        four.next = two;

        boolean hasCircle = checkCircle(one);
        System.out.println(hasCircle);
    }

三. 两个有序的链表合并

面试有碰到过问两个有序数组合并的情况. 和这种应该类似. 就是首先比较两个链表中第一个元素的值. 把较小节点的作为新链表的头结点.移动节点到下一个位置. 然后在循环体中比较. 较小的放到新链表中. 并移动到下一个节点的位置. 最后考虑一种情况. 有可能一个链表已经移动到尾节点. 这时候把另外一个链表剩余的那部分节点.添加到新链表. 并返回新链表.

**
     * 合并两个有序链表
     *
     * @param list1 链表1
     * @param list2 链表2
     * @return 合并后的链表
     */
    private Node merge(Node list1, Node list2) {
        Node head;

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        if (list1.data < list2.data) {
            head = list1;
            list1 = list1.next;
        } else {
            head = list2;
            list2 = list2.next;
        }

        Node current = head;
        while (list1 != null && list2 != null) {
            if (list1.data < list2.data) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;

        }
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        return head;
    }

@Test
    public void mergeTest() {
        Node one = new Node(1, null);
        Node two = new Node(2, null);
        Node three = new Node(3, null);
        Node four = new Node(4, null);
        Node five = new Node(5, null);

        one.next = three;
        three.next = five;
        two.next = four;

        Node list1 = one;
        Node list2 = two;

        print(list1);
        print(list2);
        Node mergeList = merge(list1, list2);
        print(mergeList);
    }

四. 删除倒数第K个节点

我先跑,如果你能追上我. 我就跟你嘿嘿嘿. 就是这么骚气. 我怎么知道倒数第K个节点. 这里也是用两个指针. fast 指针先跑K个单位. slow这时候开始跑. fast跑到结尾的时候. slow此时的位置恰好就是倒数第K个位置.
这就把问题转化成小学数学题了.

/**
     * 删除倒数第k个数据
     *
     * @param list
     * @param k
     */
    private Node deleteLastKTest(Node list, int k) {
        int i = 1;
        Node slow = list;
        Node fast = list;
        while (fast != null && i < k) {
            fast = fast.next;
            i++;
        }

        if (fast == null) {
            return list;
        }

        Node pre = null;
        while (fast.next != null) {
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }


        if (pre == null) {
            list = list.next;
        } else {
            pre.next = pre.next.next;
        }
        return list;


    }

@Test
    public void deleteLastKTest() {
        Node one = new Node(1, null);
        Node two = new Node(2, null);
        Node three = new Node(3, null);
        Node four = new Node(4, null);
        Node five = new Node(5, null);

        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;

        int k = 5;
        Node node = deleteLastKTest(one, k);
        print(node);
    }

五. 求链表的中间结点

快慢指针. 一个二倍速fast. 一个一倍速slow. fast 走到结尾. slow恰好走一半.

 /**
     *  返回中间节点
     * @param list
     * @return
     */
    private Node middleNode(Node list) {
        if(list==null){
            return null;
        }
        Node fast = list;
        Node slow = list;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

 @Test
    public void middleNodeTest() {
        Node one = new Node(1, null);
        Node two = new Node(2, null);
        Node three = new Node(3, null);
        Node four = new Node(4, null);
        Node five = new Node(5, null);
        Node six = new Node(6,null);

        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        five.next = six;

        Node node = middleNode(one);
         System.out.println(node.data);
    }