题目链接

牛客在线oj题——反转链表

题目描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：

题目示例

示例1

输入：
{1,2,3}

返回值：
{3,2,1}

示例2

输入：
{}

返回值：
{}

说明：
空链表则输出空

思路1

使用三个指针维护链表的前后关系，前指针和中指针改变链表的指向关系，后指针用于迭代三个指针，直到最后后指针为空，再次改变一次前中两个指针的指向关系即可

例如，首先定义好left，mid，right指针指向

更改left和mid之间的指向关系，mid.next = left

迭代left，mid，right指针，left = mid, mid = right, right = right.next

继续重复上述操作，直到right == null

这时，还需要再改变一下left和mid的指向，并且，第一个节点的指向还是第二个节点，这样会形成循环列表，应该将其next置为null

思路1完整代码

public class Solution {public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}}public ListNode ReverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode left = head;ListNode mid = left.next;ListNode right = mid.next; //可能为nullwhile(right != null){mid.next = left;left = mid;mid = right;right = right.next;}mid.next = left;head.next = null;return mid;}
}

思路2

可以直接遍历链表，拿出链表中的每一个值，头插到新链表中即可获得反转后的链表

定义tmp和cur指针

将tmp指向的节点头插到新链表中

然后将tmp = cur, cur = cur.next

重复上述操作，直到cur为空

思路2完整代码

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = null;ListNode cur = head;while(cur != null){ListNode tmp = cur;cur = cur.next;tmp.next = newHead;newHead = tmp;}return newHead;}
}