Home > Article > Backend Development > Python data structure flipped linked list
Flip a linked list
Example: Given a linked list 1->2->3->null, the flipped linked list is 3- >2->1->null
A relatively simple method is to use the "extraction method". That is to first create a new empty node, then traverse the entire linked list, and make the traversed nodes point to the head node of the newly created linked list.
For example, the steps are as follows:
1. Create a new empty node: None
2. 1->None
3. 2->1->None
4. 3->2->1->None
The code is very simple:
""" Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ def reverse(self, head): temp = None while head: cur = head.next head.next = temp temp = head head = cur return temp # write your code here
Of course, there is a slightly more difficult solution. We can write the code for in-place flipping of the nodes in the linked list by sequentially picking and linking them:
""" Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ def reverse(self, head): if head is None: return head dummy = ListNode(-1) dummy.next = head pre, cur = head, head.next while cur: temp = cur # 把摘链的地方连起来 pre.next = cur.next cur = pre.next temp.next = dummy.next dummy.next = temp return dummy.next # write your code here
It should be noted that when picking When chaining, don’t forget to connect the removed parts again
Thank you for reading, I hope it can help everyone, thank you everyone for supporting this site!
For more articles related to flipping linked lists of Python data structures, please pay attention to the PHP Chinese website!