Original link: https://1byte.io/how-to-reverse-a-linked-list/
“How to reverse a linked list?” is a question that gets asked a lot in interviews. Occasionally in the interviews I participated in, we were asked by our own interviewer.
If you go to another company for an interview and are asked this question, if the answer given is (using Python as an example):
def reverse ( l ) : l . reverse ( ) return l
or it could be:
def reverse ( l ) : return l [ : : - 1 ]
It will definitely be rejected. What the interviewer expects is that you define the nodes yourself, and then define the linked list:
class Node : def __init__ ( self , data ) : self . data = data self . next = None class LinkedList : def __init__ ( self ) : self . head = None # 以下略，问ChatGPT 就可以了。
But since it is a question that has been asked excessively, if you encounter it, you might as well give an answer that the interviewer has never seen before.
For example, to construct a linked list:
def cons ( h , t ) : return lambda f : f ( h , t )
Take the head:
def car ( l ) : return l ( lambda h , _ : h )
Tail:
def cdr ( l ) : return l ( lambda _ , t : t )
reverse:
def reverse ( l ) : rev = lambda l , r : rev ( cdr ( l ) , cons ( car ( l ) , r ) ) if l else r return rev ( l , None )
The above is the complete answer. In order to demonstrate the convenience of writing a function to print the linked list:
def printl ( l ) : toStr = lambda l : str ( car ( l ) ) + ' ' + toStr ( cdr ( l ) ) if l else '' print ( '(' , toStr ( l ) , ')' )
Write an example to try:
l = cons ( 1 , cons ( 2 , cons ( 3 , cons ( 4 , None ) ) ) ) printl ( l ) printl ( reverse ( l ) )
The output is:
( 1 2 3 4 ) ( 4 3 2 1 )
This should be the shortest answer to constructing a linked list by yourself, but there is a certain risk of being taken away by the interviewer for strange reasons. If you are an interviewer and want to ask this question again, you have to understand various implementation methods to avoid rejecting people who should not be rejected. 
This article is transferred from: https://1byte.io/how-to-reverse-a-linked-list/
This site is only for collection, and the copyright belongs to the original author.