给定链表 1 -＞ 2 -＞ ... -＞ n-1 -＞ n，使用 O(1) 空间复杂度使其变为 1 -＞ n -＞ 2 -＞ n-1 -＞_给定链表 1 -> 2 -> ... -> n-1 -> n,使用 o(1) 空间复杂度使其变为 1

在小林的推文里看到字节面试的一个算法题， 自己写了代码通过了，记录一下

思路：可以看到想要实现的就是将链表结尾的节点逐个移动到开头每个节点的间隙，所以可以考虑把数组分为两部分，分为前半部分 和后半部分，然后分别对这两部分处理（主要是后半部分）。将链表分为长度相近的两部分：分别以left和right为两部分起始节点，将right为头结点的链表反转，从反转后的链表的第一个节点逐渐向后将每个节点插入left为头节点的节点间隙中。这样说可能有点抽象，举个栗子：

比如以：1->2->3->4->5->6->7->8->9为例，按照题目要求预期的输出是1->9->2->8->3->7->4->6->5

1、利用快慢指针将链表分为长度相近的两部分，其实就是n/2，但是要考虑n可能为奇数，所以是长度相近的两部分。

我们可以使用快慢指针来找到中间的那个节点，快指针fast每次移动两个节点，满指针slow每次移动一个节点，这样每次就可以找到中间的那个值。比如，开始时是这样的

每次判断如果快指针的后面两个节点不为空则继续向后移动，最后会变成这样：

2、反转后半部分链表

根据slow慢指针可以确定节点6之后的链表 就是需要反转的链表，要将后面的节点插入到两个节点之间，所以前半部分的节点可以不用改变顺序，只要保持原顺序，作为基础链表等待后半部分节点的插入就可以（这里我可能没表述清楚，但是自己举两个例子就能明白啦）。反转后的链表是这样：

3、将反转后的链表节点逐个向前移动

代码：

public class ListNode {
        private Integer val;
        private ListNode next;
        public ListNode(int val){
            this.val=val;
            this.next=null;
        }

    public  static ListNode solution(ListNode head){
    //小于三个节点时不需要处理
        if(head==null||head.next==null||head.next.next==null)return head;
        ListNode slow=head;//慢指针
        ListNode fast=head.next;//快指针
        while((fast.next!=null) && (fast.next.next!=null)){
        //快慢指针移动找到“中间”节点
            slow=slow.next;
            fast=fast.next.next;
        }
        //反转开始的节点
        ListNode startNode=slow.next.next;
        ListNode last =reverseList(startNode);
        slow.next.next= last;//将反转前的节点指向反转后的链表头
        ListNode node=slow.next;//标记中间节点
        ListNode pre=head;
        
        while(node.next!=null){
        //向前插入节点
            node.next=last.next;
            last.next=pre.next;
            pre.next=last;
            pre=last.next;
            last=node.next;
        }
        return head;
    }

    public static ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode pre=null;//当前节点的前一节点
        ListNode cur=head;
        ListNode tmp=null;
        while(cur!=null){
            tmp=cur.next;//临时节点保存当前节点的下一节点 否则会丢失
            cur.next=pre;//将当前节点指向前一节点
            pre=cur;//pre指针后移
            cur=tmp;//cur指针后移
        }
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

结束！小菜鸡的一点小记录，轻喷