problem:
Given an array, build a linked list then reverse it.For example, given an array [1, 2, 3, 4, 5]
build a linked list 1 -> 2 -> 3 -> 4 -> 5
then reverse the linked list to get 5 -> 4 -> 3 -> 2 -> 1
solution:
/*
reverse a linked list
given an array
build a linked list, then reverse it.
for example: given an array [1, 2, 3, 4, 5]
build a linked list 1 -> 2 -> 3 -> 4 ->5
after reverse 5 -> 4 -> 3-> 2 -> 1
*/
//time O(N), space O(1)
class Solution {
public static void main(String...args) {
Solution solution = new Solution();
Node head = solution.generateList();
solution.printList(head);
head = solution.reverse(head);
solution.printList(head);
}
private void printList(Node head) {
System.out.println();
while(head.next != null) {
System.out.print(head.val + " -> ");
head = head.next;
}
System.out.print(head.val);
System.out.println();
}
private Node generateList() {
int[] a = new int[] {1, 2, 3, 4, 5};
Node head = new Node(a[a.length - 1], null);
for(int i = a.length - 2; i >= 0; i--) {
head = new Node(a[i], head);
}
return head;
}
private Node reverse(Node head) {
Node pre, cur, next = null;
cur = head;
next = cur.next;
cur.next = null;
pre = cur;
cur = next;
while(cur.next != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
cur.next = pre;
return cur;
}
private class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
}
