反转链表

时间复杂度O(n),空间复杂度O(1)

    /**
     * 反转链表:指针指向前一个节点
     * O(n),S(1)
     */
    public static ListNode reverse(ListNode head){
        ListNode pre = null;//当前节点的上一个
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;//指针指向前一个节点
            pre = head;//给前一个节点赋值
            head = next; //继续下一个
        }
        return pre;
    }

取中间的点

当时偶数个时,则取前一个节点

    /**
     * 取中间的点（当时偶数个时,则取前一个节点）
     * @param head
     * @return
     */
    public static ListNode getMid(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 static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        //取中间节点
        System.out.println(getMid(node1).value);//2

        //反转:
        MyList.traverse(reverse(node1));//3 2 1
    }

合并两个有序链表

递归方式

    /**
     * 合并两个有序节点链表(通过递归方式)
     */
    public static ListNode mergeToList1(ListNode head1,ListNode head2){
        if(head1 == null && head2 == null){
            return null;
        }
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }

        ListNode head = null;
        if(head1.value > head2.value){
            head = head2;
            head.next = mergeToList1(head1, head2.next);
        }else{
            head = head1;
            head.next = mergeToList1(head1.next, head2);
        }
        return head;
    }

非递归方式

    /**
     * 合并两个有序节点链表(通过非递归方式)
     */
    public static ListNode mergeToList2(ListNode head1, ListNode head2){
        if(head1 == null || head2 == null){
            return head1 != null ? head2 : head1;
        }

        ListNode head = head1.value < head2.value ? head1 : head2;
        ListNode cur1 = head == head1 ? head1 : head2;//取头结点所在的链表
        ListNode cur2 = head == head1 ? head2 : head1;//取另外一个链表

        ListNode pre = null;//cur1前一个节点
        ListNode next = null;//cur2后一个节点
        boolean notFirst = false;

        while(cur1 != null && cur2 != null){
            if(cur1.value <= cur2.value){
                if(notFirst){
                    pre.next = cur1;
                }
                pre = cur1;//当前节点

                cur1 = cur1.next;

                notFirst = true;
            }else{
                next = cur2.next;

                pre.next = cur2;//插入一个
                pre = cur2;//当前节点

                cur2 = next;//当前节点的下一个
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;//head和pre链接是在第一次
    }

测试结果

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node3;
        node2.next = node4;

//        MyList.traverse(mergeToList1(node1, node2));//1 2 3 4

        MyList.traverse(mergeToList2(node1, node2));//1 2 3 4
    }