目录

一、题目内容

二、解题思路 

三、代码

一、题目内容

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

二、解题思路 

先按照顺序存储节点，然后首尾指针依次连接即可，如果首尾指针正好重合，则末尾next添加重合的元素即可，否则next为空。

注：link为后半段链表连接的节点。

三、代码

  

   

    

     

    
    

     

      # 2020-10-20
     
    
   

    

     

    
    

     

      # Definition for singly-linked list.
     
    
   

    

     

    
    

     

      class ListNode:
     
    
   

    

     

    
    

     
 def __init__(self, val=0, next=None):
     
    
   

    

     

    
    

     

       self.val = val
     
    
   

    

     

    
    

     

       self.next = next
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def __repr__(self):
     
    
   

    

     

    
    

     
 return str(self.val)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def reorderList(self, head: ListNode) -> None:
     
    
   

    

     

    
    

     
 """
     
    
   

    

     

    
    

     

       Do not return anything, modify head in-place instead.
     
    
   

    

     

    
    

     

       """
     
    
   

    

     

    
    

     

       cache = []
     
    
   

    

     

    
    

     

       node = head
     
    
   

    

     

    
    

     
 while node:
     
    
   

    

     

    
    

     

       cache.append(node)
     
    
   

    

     

    
    

     

       node = node.next
     
    
   

    

     

    
    

     

       i, j = 0, len(cache) - 1
     
    
   

    

     

    
    

     

       link = ListNode()
     
    
   

    

     

    
    

     
 while i < j:
     
    
   

    

     

    
    

     

       link.next = cache[i]
     
    
   

    

     

    
    

     

       link = cache[i].next = cache[j]
     
    
   

    

     

    
    

     

       i += 1
     
    
   

    

     

    
    

     

       j -= 1
     
    
   

    

     

    
    

     
 if i == j:
     
    
   

    

     

    
    

     

       link.next = cache[i]
     
    
   

    

     

    
    

     

       cache[i].next = None
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       link.next = None
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       head_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     
    
   

    

     

    
    

     

       head = ListNode(head_list[0])
     
    
   

    

     

    
    

     

       p = head
     
    
   

    

     

    
    

     

       i = 1
     
    
   

    

     

    
    

     
 while p is not None:
     
    
   

    

     

    
    

     

       p.next = ListNode(head_list[i])
     
    
   

    

     

    
    

     

       i += 1
     
    
   

    

     

    
    

     

       p = p.next
     
    
   

    

     

    
    

     
 if i == len(head_list):
     
    
   

    

     

    
    

     
 break
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       s.reorderList(head)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/109183948