leetcode - 反转链表

反转一个单链表。

示例:

输入: 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;
}