链表与栈——数组入栈出栈、单链表翻转

小咪咪 2022-05-12 14:38 286阅读 0赞

#### 数组入栈出栈 ####

class Stack{
    	private Object[] data = new Object[0];	//栈的内容
    	private int size = 0;	//栈的元素个数
    
    	public boolean isFull(){	//判断栈是否满
    		return data.length == size;
    	}
    	public boolean isEmpty(){	//判断栈是否空
    		return size == 0;
    	}
    	public void addData(){		//扩容
    		data  = Array.copyOf(data,data.length+10);
    	}
    
    	public void push(Object obj){	//入栈操作
    		if(isFull()){
    			addData();
    		}
    		size++;
    		data[size-1] = obj;
    	}
    	public Object pop(){	//出栈操作
    		Object o = data[size-1];
    		data[size-1] = null;
    		size--;
    		return o;
    	}
    }
    
    public class stackTest{
    	public static void main(String[] args){
    		Stack s = new Stack();
    		s.push(1);
    		s.push("123");
    		Objct o = s.pop();
    		System.out.println(o);
    	}
    }

#### 单链表翻转 ####

![在这里插入图片描述][70]  
链表定义

class ListNode {
        int val;
        ListNode next;
    
        ListNode(int x) {
            val = x;
        }
    }

非递归实现很简单，只需要遍历一遍链表，在遍历过程中，把遍历的节点一次插入到头部。

public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            while(head!=null){
                ListNode tmp = head.next;
                head.next = prev;
                prev = head;
                head = tmp;
            }
            return prev;
        }

递归实现：翻转head->为首的链表， 然后head变为尾部节点

public ListNode reverseList(ListNode head) {
            if(head==null||head.next ==null)
                return head;
            ListNode prev = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return prev;
        }

[70]: /images/20220504/bb33f8b3b5714088ab722566434ab57e.png