当前位置：网站首页>Link list of daily Niuke questions

Given the head node of a single linked list pHead( The header node has a value , For example, in the figure below , its val yes 1), The length is n, After reversing the linked list , Return the header of the new linked list .
Data range :0≤n ≤1000
requirement : Spatial complexity O(1), Time complexity O(n).
For example, when entering a linked list {1,2,3} when ,
After reversal , The original linked list becomes {3,2,1}, So the corresponding output is {3,2,1]. The above conversion process is shown in the figure below :

Ideas 1

While traversing the linked list modify next Point to

Code 1

public ListNode ReverseList(ListNode head) {
        ListNode tmp = null;
        while(head != null) {
            ListNode node = head.next;
            head.next = tmp;
            tmp = head;
            head = node;
        }
        return tmp;
    }

Complexity 1

Time complexity O(N): Traversing the linked list uses linear size time .
Spatial complexity O(1): Variable tmp and head Use constant size for extra space .

Ideas 2

Consider using recursion to traverse the linked list , When the tail node is crossed, the recursion is terminated , Modify the of each node during backtracking next Reference point .
recur(cur,pre) Recursive function :
1. Termination conditions : When cur It's empty , Returns the tail node pre( That is, reverse the head node of the linked list );⒉. Recursive successor node , Record return value ( That is, reverse the head node of the linked list ) by res ;
3. Modify the current node cur The reference points to the precursor node pre ;
4. Returns the header node of the inverted linked list res ;
reverseList(head) function :
Call and return recur(head,null). Pass in null Because after reversing the linked list ,head The node points to null ;

Code 2

class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    //  Call recursion and return 
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; //  Termination conditions 
        ListNode res = recur(cur.next, cur);  //  Recursive successor node 
        cur.next = pre;              //  Modify the node reference to 
        return res;                  //  Returns the header node of the inverted linked list 
    }
}

Complexity 2

Time complexity O(N) : Traversing the linked list uses linear size time .
Spatial complexity O(N): The recursive depth of traversing the linked list reaches N, System use O(N) Size extra space .

subject 2 The linked list of returns from end to end

Enter the head node of a linked list , Returns the value of each node from the end to the end of the linked list

Ideas 2.1

Reverse the list Then traverse and save List Output （ The stupidest way ）

Code 2.1

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null) {
            return new ArrayList();
        }
        ListNode node = ReverseList(listNode);
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(node != null) {
            list.add(node.val);
            node = node.next;
        }
        return list;
        
    }
   public ListNode ReverseList(ListNode head) {
        ListNode tmp = null;
        while(head != null) {
            ListNode node = head.next;
            head.next = tmp;
            tmp = head;
            head = node;
        }
        return tmp;
    }
}

Complexity 2.1

Ideas 2.2

Stack
The stack is characterized by last in, first out , That is, the last element pushed into the stack pops up first . Considering this feature of stack , Use the stack to invert the order of linked list elements . Start from the head node of the linked list , Push each node into the stack in turn , Then pop up the elements in the stack in turn and store them in the array .· Create a stack , The node used to store the linked list
· Create a pointer , Initially, it points to the head node of the linked list · When the element pointed to by the pointer is not null , Repeat the following :
. Push the node pointed to by the pointer into the stack
. Move the pointer to the next node of the current node
· Get the size of the stack size, Create a collection print, Its size is size
· repeat size Perform the following operations :
. Pop up a node from the stack , Save the value of this node to list
· return print

Code 2.2

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = listNode;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        ArrayList print = new ArrayList(size);
        for (int i = 0; i < size; i++) {
            print.add(stack.pop().val);
        }
        return print;
    }
}