网站建设推广专员岗位职责,济南做企业网站公司,网站开发人才需求,网站一级页面标题怎么做的反转链表在解决需要从尾节点开始遍历到头节点的地方很实用#xff0c;是一种常用的解题技巧。在反转时#xff0c;我们可以考虑从前向后反转和从后向前反转两种方式。
法一#xff1a;递归 每次将链表的头节点的下一个节点作为新的头节点#xff0c;然后对剩余部分调用递归… 反转链表在解决需要从尾节点开始遍历到头节点的地方很实用是一种常用的解题技巧。在反转时我们可以考虑从前向后反转和从后向前反转两种方式。
法一递归 每次将链表的头节点的下一个节点作为新的头节点然后对剩余部分调用递归函数。这样递归调用会一直执行直到到达链表的尾部从链表的尾部开始逆序地将节点连接起来。
public ListNode reverseList(ListNode head) {// 如果链表为空或只有一个节点直接返回该链表因为反转一个节点或空链表都是其本身if (head null || head.next null) {return head;}// 将链表的头节点的下一个节点作为新的头节点ListNode resetHead head.next;// 对剩余部分调用递归函数得到反转后的链表ListNode reversedReset reverseList(resetHead);// 将原头节点的下一个节点指向头节点形成反转后的链表resetHead.next head;// 将原头节点的下一个节点指向 null断开原头节点和反转后的链表的连接head.next null;// 返回反转后的链表即为新的头节点return reversedReset;
}该方法的时间复杂度是On空间复杂度是On。
法二三指针 在从前向后反转链表时如果将某一节点的next指针指向它的前一个节点那么余下尚未反转的部分就会因链表断开而丢失所以为了保证不丢失我们需要指针去记录它们。因此需要三个指针分别指向当前遍历到的节点它的前一个节点和后一个节点。 public ListNode reverseList(ListNode head) {// 初始化前一个节点为 null当前节点为链表头ListNode prev null;ListNode cur head;// 遍历链表直到当前节点为 nullwhile (cur ! null) {// 保存当前节点的下一个节点以防失去链表连接ListNode next cur.next;// 将当前节点的 next 指针指向前一个节点实现反转操作cur.next prev;// 更新 prev 为当前节点cur 更新为下一个节点prev cur;cur next;}// 返回反转后链表的头节点return prev;} 该方法的时间复杂度是On空间复杂度是O1。
