做微网站的公司哪家好呢,南宁网站建设托管,wordpress能开发商城网站,wordpress底部功能按钮反转一个单链表
题意#xff1a;反转一个单链表。 示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL
思路
需要虚拟节点么#xff1f; 答#xff1a;不需要#xff0c;因为没有删除节点#xff0c;只是改变了节点的指向。 遍…反转一个单链表
题意反转一个单链表。 示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL
思路
需要虚拟节点么 答不需要因为没有删除节点只是改变了节点的指向。 遍历之后如果找到之前的节点 答双指针。我们利用双指针来标识前一个节点。 首先我们为什么需要前一个节点 答因为当前节点的下一个节点需要指向前一个节点。所以需要下一个节点。 给兄弟们上一个动图就明白一切了。
代码
//class ListNode{
// private int val;
// private ListNode next;
// ListNode(int val){
// this.val val;
// }
// ListNode(int val,ListNode next){
// this.val val;
// this.next next;
// }
//}
public class reverseTreeTest {//1. 双指针法public ListNode reverserTree(ListNode head) {ListNode prev null;ListNode cur head;ListNode temp;while (cur ! null) {//步骤一记录下下一个节点temp cur.next;//步骤二当前节点指向前一个节点cur.next prev;//步骤三之前的节点变成cur节点因为1-null 之后当遍历2的时候需要 2-prev1-null,如果这里不赋值会变成2-nullprev cur;//步骤四当前节点变成下一个节点cur temp;}return prev;}}总结
双指针法在解决链表的时候是一种常见的算法。比如后面的链表中寻找环也是利用双指针快慢指针相遇来判断是否有环。 这个题目唯一需要注意的是虽然只有4行代码。但是你得理解每行代码的意义。实在不行自己手动画一画也就理解了。如果还是理解不了先记着吧后面熟能生巧。嘻嘻。
