leetcode - 反转链表

  1. 反转一个单链表。

    示例:

    输入: 1->2->3->4->5->NULL

    输出: 5->4->3->2->1->NULL

    /**
     * Definition for singly-linked list.
     */
    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }
    
    /**
     * 反转链表
     * 1. 遍历链表, 使用集合保存数据元素, 新声明一个链表, 遍历集合复制 时间复杂度是O(n)
     * 2. 声明两个链表, 直接反转(有种数组中两个元素交换的感觉)
     * <p>
     *     输入: 1->2->3->4->5->NULL
     *     输出: 5->4->3->2->1->NULL
     * <p/>
     * 执行用时 :0 ms, 在所有 java 提交中击败了100.00%的用户
     * 内存消耗 :37 MB, 在所有 java 提交中击败了45.52%的用户
     * @param head  链表头
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode cur = head,
                pre = null,
                temp = null;
        while(cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    
    /**
     * 执行用时 :3 ms, 在所有 java 提交中击败了 7.38%的用户
     * 内存消耗 :36.8 MB, 在所有 java 提交中击败了50.79% 的用户
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        if(head == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        while(head != null) {
            list.add(0,head.val);
            head = head.next;
        }
        ListNode result = new ListNode(list.get(0));
        ListNode temp = result;
        for (int i = 1; i < list.size(); i++) {
            ListNode node = new ListNode(list.get(i));
            result.next = node;
            result = node;
        }
        return temp;
    }
    
    // 测试
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    ListNode node5 = new ListNode(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    ListNode node = reverseList(node1);
    while (node != null) {
        System.out.println(node.val);
        node = node.next;
    }
相关文章
相关标签/搜索