牛客网剑指offer编程题记录

思路

JZ6 从尾到头打印链表（简单）

题目描述：

思路1（非递归，通过）

从头到尾遍历，边遍历边存进栈，最后从栈弹出来打印。时间复杂度O(n)，空间复杂度O(n)

 public ArrayList printListFromTailToHead(ListNode listNode) {
        ArrayList list = new ArrayList();
        Stack stack = new Stack();
        ListNode p = listNode;
        while(p!=null){
            stack.push(p.val);
            p = p.next;
        }
        while(!stack.empty()){
            list.add((Integer) stack.peek());
            stack.pop();
        }
        return list;
    }

 思路一，通过。

思路2（递归，栈内存溢出）

递归打印，不是空则传入next递归，当从下一层返回时说明当前节点后面的节点内容全部打印完，所以把当前节点值加入结果列表。时间复杂度O(n)，空间复杂度O(n)

import java.util.ArrayList;
public class Solution {
    ArrayList list = new ArrayList();
    public ArrayList printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

思路2的代码跑起来栈内存溢出 Exception in thread "main" java.lang.StackOverflowError

JZ24 反转链表 题目描述

思路1（通过）

 

 public ListNode ReverseList(ListNode head) {
      if(head==null) return null;
      ListNode p = head.next;
      ListNode newHead = head;
      head.next = null;
      while(p!=null){
          ListNode q = p.next;
          p.next = newHead;
          newHead = p;
          p = q;
      }  
      return newHead;  
    }

 

 JZ25 合并两个排序的链表 题目描述

思路1

用一个新节点做新链表表头，两个指针分别遍历两条链表，取两个指针中小的一个链接到新链表表尾，重置新链表表尾指针、被链接到新链表的那个指针后移，直至其中一个指针到达链表尾，将还未到链表尾的那条链表直接链接到新链表上。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode p=list1,q=list2;
        //用一个新节点做新链表表头
        ListNode newHead = new ListNode(0);
        //r用来表示新链表表尾
        ListNode r = newHead;
        while(p!=null && q!=null){
             //取其中较小值链接到新链表，被选中的那个指针需要后移
            if(p.val<=q.val){
                r.next = new ListNode(p.val);
                p = p.next;
            }else{
                 r.next = new ListNode(q.val);
                q = q.next;
            }
            //更新新链表尾指针
            r = r.next;
        }
        if(q!=null) p=q;
        //把未遍历到尾的长链表剩下节点全部接到新链表尾
        while(p!=null){
            r.next = new ListNode(p.val);
            p = p.next;
            r = r.next;
        }
        return newHead.next;
    }
}