智慧团建网站pc端,江门网站建设设计,创作图片的软件,成都网站建设优化推题目说明
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
方法一#xff1a;头插法反转链表
思路#xff1a;
声明p指针指向原头节点#xff0c;并将头节点置空#xff1b;p指针循环原链表将元素用头节点插入法逐个插入head中请你反转链表并返回反转后的链表。
方法一头插法反转链表
思路
声明p指针指向原头节点并将头节点置空p指针循环原链表将元素用头节点插入法逐个插入head中head为反转后链表头整个循环完毕我们就能得到反转后的链表了存储在head中。 head A - B - C - D - null p head ; head null; head null ; A插入head p.next head.next; head p; head A - null B插入head head B - A - null C插入head head C - B - A - null D插入head head D - C - B - A - null 整个反转完成
/*** 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; }* }*/
class Solution {public ListNode reverseList(ListNode head) {
ListNode phead;
ListNode nextnull;
head null;
while(p!null){nextp.next;p.nexthead;headp;pnext;
}
return head;}
}算法分析
时间复杂度为O(n) 空间复杂度为O(1)
方法二双指针局部反转 * head 1 - 2 - 3 - 4 - null* null - 1 2 - 3 - 4 - null* null - 1 - 2 3 - 4 - null* null - 1 - 2 - 3 4 - null* null - 1 - 2 - 3 - 4 head思路 1.声明cur和next两个指针用cur指针指向当前需要处理节点next指向cur下一个节点 2.cur起点为nullnext起点为头节点 3.将next的后续节点指向cur这样就把next和原链表分离开来了next和cur分别前进一步 4.继续3直到next为nullcur就是反转后链表的头结点 思考1为什么cur要从null开始从第一个节点开始可以吗为什么
/*** 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; }* }*/
class Solution {public ListNode reverseList(ListNode head) {/*** head 1 - 2 - 3 - 4 - 5 - null * null - 1 2 - 3 - 4 - 5 - null * null - 1 - 2 3 - 4 - 5 - null * ...* null - 1 - 2 - 3 - 4 - 5 head* 1.用cur指针指向当前需要处理节点next指向cur下一个节点* 2.将cur next进行局部反转* 3.cur和next前进一步继续2直到next指向链尾*/ListNode curnull;ListNode nexthead;ListNode tmpnull;while(next!null){tmp next.next;next.nextcur;// 前进一步curnext;nexttmp; }return cur;}
}方法三递归反转
解题思路 1.递归到最后一个节点作为表头节点即为revHead 2.在递归函数逐步返回的过程中将当前节点的后续节点指向当前节点 3.再当前节点后续节点置空和原有链表分离对于反转前链表的非头节点来讲不是必须的为了简单统一处理 4.完成2-3步就完成一次局部反转直到第一个调用处理完毕就得到反转后的链表
如下过程所示 head 1 - 2 - 3 - 4 - 5 - null head 1 - 2 - 3 - 4 - 5 revHead head 1 - 2 - 3 - 4 null - 4 - 5 revHead head 1 - 2 - 3 null - 3 - 4 - 5 revHead head 1 - 2 - 3 null - 2 - 3 - 4 - 5 revHead head 1 - null null - 1 - 2 - 3 - 4 - 5 revHead revHead 5 - 4 - 3 - 2 - 1 - null
递推公式 node.next.next node node.next null
终止条件 node.next null
/*** 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; }* }*/
class Solution {public ListNode reverseList(ListNode head) {/*** 1.递归到最后一个节点作为表头节点即为revHead* 2.在递归函数逐步返回的过程中将当前节点的后续节点指向当前节点* 3.再当前节点后续节点置空和原有链表分离对于反转前链表的非头节点来讲不是必须的为了简单统一处理* 4.完成2-3步就完成一次局部反转直到第一个调用处理完毕就得到反转后的链表* revHead* head 1 - 2 - 3 - 4 - 5 - null* head 1 - 2 - 3 - 4 - 5 revHead* head 1 - 2 - 3 - 4 null - 4 - 5 revHead* head 1 - 2 - 3 null - 3 - 4 - 5 revHead* head 1 - 2 - 3 null - 2 - 3 - 4 - 5 revHead* head 1 - null null - 1 - 2 - 3 - 4 - 5 revHead* revHead 5 - 4 - 3 - 2 - 1 - null*/// 空判定if(head null){return null;}// 递归终止条件递归到最后一个节点时返回作为反转后链表的头结点if(head.next null){return head;}ListNode revHead reverseList(head.next);// 倒数第二个节点开始对示例而言节点4才会进入到下面的逻辑head.next.next head;head.next null;return revHead;}
}算法分析 时间复杂度O(n) 空间复杂度O(n)
思考
思考1为什么cur要从null开始从第一个节点开始可以吗为什么
cur不一定非得初始为null也可以从第一个节点开始只不过要额外处理一下头结点的逻辑即第一个节点的时候需要把cur的后继节点置为空 并且next的后续节点置为cur 这样后续的操作就是一样的了。 public ListNode reverseList(ListNode head) {ListNode curhead;ListNode nexthead.next;cur.nextnull;ListNode tmpnull;while(next!null){tmp next.next;next.nextcur;// 前进一步curnext;nexttmp;}return cur;}
