leetcode143.重排链表_给定一个单链表:l0→l1→l2→…→ln-2→ln-1→ln,如{1,2,3,4,5,6}

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

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

解答：
方法一：把链表节点放进数组中，并对其重新排列

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        
        vec = list()
        node = head
        while node:
            vec.append(node)
            node = node.next
        
        i, j = 0, len(vec) - 1
        while i < j:
            vec[i].next = vec[j]
            i += 1
            if i == j:
                break
            vec[j].next = vec[i]
            j -= 1
        
        vec[i].next = None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

方法二：把链表放进数组中，然后通过双指针法，一前一后，来遍历数组，构造链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        res=[]
        cur=head
        length=0
        while cur:
            res.append(cur)
            length+=1
            cur=cur.next
        
        cur=head
        i=1
        j=length-1
        #count:计数，偶数取后面，奇数取前面
        count=0
        while i<=j:
            if count%2==0:
                cur.next=res[j]
                j-=1
            else:
                cur.next=res[i]
                i+=1
            cur=cur.next
            count+=1
        cur.next=None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

方法三：

方法四：