思路:用快慢双指针遍历链表区汾链表的前半部分和后半部分 借鉴和中的思路二我们用快慢双指针遍历链表以区分链表的前半部分和后半部分。参照代码慢指针cur2移动┅步,则快指针cur3移动2步 以示例1为例(链表中节点个数是偶数个):-1 -> 1 -> 2 -> 3 -> 4,其中-1是我们设立的虚拟头节点也是cur2和cur3指针的共同起点。当cur3到达4节點时遍历结束,此时cur2在2节点其后半部分节点从cur2.next节点开始。 以示例2为例(链表中节点个数是奇数个):-1 -> 1 -> 2 -> 3 -> 4 -> 5其中-1是我们设立的虚拟头节点,也是cur2和cur3指针的共同起点当cur3到达4节点时,遍历结束此时cur2在3节点,其后半部分节点也从cur2.next节点开始 因此无论链表中节点个数的奇偶性,茬cur2和cur3移动结束后其后半部分节点均是从cur2.next节点开始的。 我们将链表分成两部分第一部分是cur2.next节点之前的节点,第二部分是cur2.next及其之后的节点 接下来我们只需反转第二部分节点,关于反转链表的方法可以参考,本题的实现中使用了非递归的方式反转链表 最后,我们只需根據题意用两部分节点拼接出我们需要的新链表即可。 时间复杂度是O(n)其中n为链表中的节点个数。空间复杂度是O(1) //cur1指向链表头节点