0%

Algorithm_链表反转

Posted on In

Define ListNode

1
2
3
4
5
6
7
8
9
public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
  1. 使用栈Stack的方式来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode reverseList(ListNode head) {

        Stack<ListNode> stack = new Stack<>();

        if (head == null) {
            return null;
        }

        ListNode cur = head;
        while (cur != null) {
            stack.push(new ListNode(cur.val));
            cur = cur.next;
        }

        cur = stack.pop();
        ListNode newListNode = cur;
        while (!stack.isEmpty()) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        return newListNode;
    }
  1. 双指针的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
  1. 递归的方式
1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode listNode = reverseList(head.next);
        listNode.next.next = listNode.next;
        listNode.next = null;
        return listNode;
    }