链表逆序 从尾到头打印节点

2018-04-16更新: 递归逆序链表

class LinkNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        if self.next is not None:
            return '{},{}'.format(self.val, self.next)
        return '{}'.format(self.val)


def reverse(cur, pre=None):
    next = cur.next
    cur.next = pre
    if next is None:
        return cur
    else:
        return reverse(next, cur)


if __name__ == '__main__':
    node = LinkNode(1, LinkNode(2, LinkNode(3, LinkNode(4))))
    print(node)
    head = reverse(node)
    print(head)

class ListNode {
    int val;
    ListNode next;
}

//链表逆序
public ListNode reverse(ListNode listNode) {
    if (listNode == null) {
            return null;
    }
    ListNode pre = null;
    ListNode cur = listNode;
    ListNode next = cur.next;

    while (next != null) {
        cur.next = pre;
        pre = cur;
        cur = next;
        next = cur.next;
    }
    cur.next = pre;
    return cur;
}

pre  cur  next
null [] -> [] -> [] -> [] -> null

cur.next = pre;pre = cur;next=cur.next;
       pre   cur  next
null <- [] x [] -> [] -> [] -> null

cur.next = pre;pre = cur;next=cur.next;
              pre  cur  next
null <- [] <- [] x [] -> [] -> null

cur.next = pre;pre = cur;next=cur.next;
                    pre  cur   next
null <- [] <- [] <- [] x [] -> null

cur.next = pre;
                          cur
null <- [] <- [] <- [] <- [] x null


//链表逆序(使用栈做辅助)
public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    while (!stack.isEmpty()) {
        head = stack.pop();
    }
    return head;
}


//从尾到头打印节点(使用栈做辅助)
public ArrayList<Integer> reList(ListNode head) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    while (head != null) {
        stack.push(head.val);
    }
    while (!stack.isEmpty()) {
        arrayList.add(stack.pop());
    }
    return arrayList;
}

两个栈实现队列的功能

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }

        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }

        return stack2.pop();
    }
}

---