Hot100题3--反转链表

反转链表问题

原本我想的是模拟两个指针一个指向头节点一个指向头节点的下一个节点，但是这既不能正确处理边界条件也不能返回反转后的头指针，而且容易产生空指针异常，随即启用，新方法仍旧是两个指针，不过分为前驱和当前节点，前驱指向空，当前节点指向head，然后进行while循环判断条件是当前节点不为空，循环体做的就是先记录一下当前节点的下一个节点，之后进行指针反转，最后将前驱和当前节点分别向后移动一步，最终循环结束返回头节点，也就是原本的尾节点，话不多说，代码如下：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ public class Solution { public ListNode reverseList(ListNode head) { // 初始化前驱节点为null，当前节点为head ListNode prev = null; ListNode current = head; // 遍历链表直到末尾 while (current != null) { // 记录下一个节点 ListNode nextTemp = current.next; // 反转当前节点的指针 current.next = prev; // 前移两个指针 prev = current; current = nextTemp; } // 返回新的头节点 return prev; } }

时间复杂度：O(n)