This page looks best with JavaScript enabled

链表问题

 ·  ☕ 1 min read

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class ListNode {
    int val;
    ListNode next;
}

/**
* 链表逆序
* 使用三个指针: pre, cur, next 完成
*/
public ListNode reverse(ListNode node) {
    if (node == null) {
        return null;
    }

    ListNode cur = node;
    ListNode pre = null;

    while (cur != null) { // 当前节点为 null 说明遍历结束了
        ListNode next = cur.next;  // 暂存当前节点的下一个节点
        cur.next = pre;   // 当前节点的 next 指向前一个节点
        pre = cur;        // 前一个节点移到当前节点
        cur = next;       // 当前节点移到下一个节点
    }

    return pre;
}
一次操作过程:

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

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

pre = cur; cur = next;
       pre  cur
            next
null <-[] x [] -> [] -> [] -> null
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
//链表逆序(使用栈做辅助)
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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
//从尾到头打印节点(使用栈做辅助)
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();
    }
}

Yang
WRITTEN BY
Yang
Developer