leetcode题后感-01

梦里梦外; 2022-08-10 04:51 68阅读 0赞

今天双11，断断续续的节日，望断天涯路！

明年就要参加工作了，作为即将入职的菜鸟，倍感压力。得提前做好准备，刷刷算法题，让自己对java的理解有所提升，而且需要仔细体味java怎么才能高效，推荐Effective Java这本书，虽然我没看，但是我也即将加入学习大军中。

对于链表的算法题，找工作的时候问的非常频繁，现在回顾一下。第一题是链表反转。

链表反转有两种方法：一种是借助于栈来实现，遍历链表，将节点的引用存入栈中，然后通过出栈来实现反转；第二种方法是定义3个引用，第一个引用指向首节点，第二个引用指向第二个节点，第三个引用始终作为第二个节点的下一个节点，需要在循环中实现，先将head的next设为null，然后进入循环，第三个引用为第二个引用的next，每次将第二个引用的next指向第一个引用，然后第一个引用指向第一个引用，第二个引用指向第三个引用。

public ListNode reverseList(ListNode head) {
            
            // 1.安全及边界问题
            if(head==null||head.next==null) return head;
            
            // 2.定义一个栈来存储遍历过的节点
            Stack<ListNode> stack=new Stack<>();
            
            // 3.遍历链表
            ListNode temp=head;
            
            while(temp!=null){
                stack.push(temp);
                temp=temp.next;
            }
            
            // 4.弹出栈中的节点
            if(!stack.isEmpty()) temp=stack.pop();
            
            ListNode res=temp;
            while(!stack.isEmpty()){
                temp.next=stack.pop();
                temp=temp.next;
            }
            temp.next=null;//注意需要有此步，表名最后一个结点的后继为空
            
            return res;
            
        }

public ListNode reverseList(ListNode head) {
            
            // 1.安全边界问题
            if(head==null||head.next==null) return head;
            
            //2.定义三个变量pre，slow用来描述新的链表（反转后的），fast用来遍历整个链表
            ListNode pre=head;
            ListNode slow=head.next;
            pre.next=null;
            ListNode fast=null;
            while(slow!=null){
                fast=slow.next;
                slow.next=pre;
                
                pre=slow;
                slow=fast;
            }
            
            return pre;
        }