Reverse a linked list

Topic describes

Enter a linked list, reverse the list, output the new list header.

Idea 1

  • Figure 3 shows an example of three nodes.

Program (Java)
     Code1 * time complexity: O(n) * time complexity: O(1) */
public ListNode ReverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = head;
    while(head ! =null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} * /
Copy the code

Idea 2

  • recursive
Program (Java)
     /** * code2 * time complexity: O(n) * time complexity: O(n) */
public ListNode ReverseList(ListNode head) {
     if (head == null || head.next == null) {
         return head;
     }

     ListNode p = reverseList3(head.next);//p, new list header
     head.next.next = head;
     head.next = null;
     return p;
}
Copy the code