输入一个偶数n(n>2),建立不带头结点的整数单链表L,L=(a1,an,a2,an-1,...,an-2,...an),其中ai=i。重新排列单链表L的节点顺序，改变为L=(a1,an,a2,an-1,...,an/2,a1)。例如，给定L为（1，2，3，4），重新排列后为（1，4，2，3）

思路：

1.首先将单链表中的所有节点存储到一个数组中，方便后续操作。

2.将数组中的节点按照题目要求重新排列，具体方法为：

（1）将数组分为两部分，前一半为奇数节点，后一半为偶数节点。

（2）将后一半的节点逆序排列。

（3）将前一半的每个节点的next指针指向后一半对应位置的节点。

（4）将后一半的最后一个节点的next指针指向前一半的第一个节点。

3.将排列好的节点重新连接成单链表。

代码实现：

typedef struct node{
int data;
struct node *next;
}Node,*LinkList;

void rearrange(LinkList L){
int n=0,i;
Node *p=L->next,*q;
while(p){
n++;
p=p->next;
}
Node *a[n];
p=L->next;
for(i=0;i<n;i++){
a[i]=p;
p=p->next;
}
for(i=0;i<n/2;i++){
a[i]->next=a[n-1-i];
}
for(i=n/2;i<n-1;i++){
a[i]->next=a[n-i-2];
}
a[n-1]->next=a[0];
L->next=a[0];
}

示例：

相关问题

输入一个偶数n(n>2),建立不带头结点的整数单链表L,L=(a1,an,a2,an-1,...,an-2,...an),其中ai=i

首先，我们需要确定链表的长度，因为链表中的元素是按照一定的规律排列的。因为题目中给定的是偶数n，所以链表的长度为n。

其次，我们需要考虑链表中每个元素的值。根据题目要求，链表中的第一个元素为1，第二个元素为n，第三个元素为2，第四个元素为n-1，以此类推，直到链表中倒数第二个元素为n/2，最后一个元素为n/2+1。

因此，我们可以按照上述规律依次构造链表。

代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def createList(n):
    head = None
    tail = None
    for i in range(1, n//2+1):
        node1 = ListNode(i)
        node2 = ListNode(n-i+1)
        if not head:
            head = node1
            tail = node2
            head.next = tail
        else:
            node1.next = tail
            tail.next = node2
            tail = node2
            tail.next = None
    return head

我们可以测试一下：

head = createList(8)
while head:
    print(head.val)
    head = head.next

输出结果为：

1
8
2
7
3
6
4
5

输入一个偶数n(n>2),建立不带头结点的整数单链表L,L=(a1,an,a2,an-1,...,an/2,...an),其中ai=i

思路：先生成一个长度为n的数组，然后将数组中的元素按照规律插入到链表中。

代码如下：

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


def create_linked_list(n):
    nums = [i for i in range(1, n+1)]
    head = ListNode(nums[0])
    p = head
    for i in range(1, n//2):
        p.next = ListNode(nums[i])
        p.next.next = ListNode(nums[n-i])
        p = p.next.next
    p.next = ListNode(n//2)
    return head


# 测试
head = create_linked_list(6)
while head:
    print(head.val, end=' ')
    head = head.next

输出：

1 6 2 5 3 4

时间复杂度：$O(n)$。