首页 > 试题广场 >

按照左右半区的方式重新组合单链表

[编程题]按照左右半区的方式重新组合单链表

热度指数：855 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个单链表的头部节点head，链表长度为N。如果N为偶数，那么前N/2个节点算作左半区，后N/2个节点算作右半区；如果N为奇数，那么前N/2个节点算作左半区，后N/2+1个节点算作右半区；左半区从左到右依次记为L1->L2->...，右半区从左到右依次记为R1->R2->...。请将单链表调整成L1->R1->L2->R2->...的样子。例如： 1->2->3->4 调整后：1->3->2->4 1->2->3->4->5 调整后：1->3->2->4->5 要求：如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

牛客447573号

Java实现的

public void relocateList(ListNode head) {// 头结点
 ListNode p1 = new ListNode(0);
 ListNode p2 = new ListNode(0);
 ListNode pre = null;
 ListNode pTemp = null;

 p1.next = head.next;
 p2.next = head.next;
 // 单链表为空或有3个元素以内（少于4个），直接返回此单链表即可
 if (head.next == null || head.next.next == null || head.next.next.next == null|| head.next.next.next.next==null)
 return;

 int length = 0, start2 = 0;
 // 取得单链表长度
 while (p2.next != null) {
 length++;
 p2.next = p2.next.next;
 }// while(p2.next!=null)
 start2 = length / 2;
 p2.next = head.next;
 while (start2 > 0 && p2.next != null) {
 pre = p2.next;
 p2.next = p2.next.next;
 start2--;
 }// while(start2>0)

 // 合并左右半区
 pre.next = null;// 得到左半区
 start2 = length / 2;
 while (start2 > 0) {
 // 左半区操作不用另考虑，右半区的结点插入过来即可
 pre = p1.next;// 插入结点时要用到pre
 p1.next = p1.next.next;

 // 处理右半区结点，头插法
 pTemp = p2.next;
 p2.next = p2.next.next;
 pTemp.next = p1.next;
 pre.next = pTemp;
 // p1.next = p1.next.next;

 start2--;
 }// while(start2>0)
 if (p2.next != null) {
 pTemp.next=p2.next;
 }// if(p2.next!=null)
 }

发表于 2015-03-13 19:17:12 回复(0)

writezen

//完整程序，放入Eclipse即可运行
class ListNode {
 public int val;
 ListNode next = null;

 ListNode(int val) {
 this.val = val;
 }
 public int getValue(){
 return this.val;
 }
 public void displayNode(){
 System.out.print(getValue()+" ");
 }
}
class LinkList{
 ListNode head;
 public void insertHead(int val){
 ListNode newNode=new ListNode(val);
 newNode.next=head;
 head=newNode;
 }
 public int getLength(){
 ListNode current=head;
 int length=0;
 while(current!=null){
 length++;
 current=current.next;
 }
 return length;
 }
 public void display(){
 ListNode current=head;
 while(current!=null){
 current.displayNode();
 current=current.next;
 }
 }
}
public class Solution {
 /**
 *	按照左右半区的方式重新组合单链表
 *	输入：一个单链表的头节点head
 *	将链表调整成题目要求的样子
 *
 *	后台的单链表节点类如下：
 **/
 
  
 static void relocateList(ListNode head) {
 LinkList list=new LinkList();
 list.head=head;
 ListNode current=head;
 ListNode otherHead=null;
 ListNode temp1=null;
 ListNode temp2=null;
 int i=0;
 while(current!=null){
 if(i==list.getLength()/2-1){
 otherHead=current.next;
 current.next=null;
 }
 i++;
 current=current.next;
 }
 current=otherHead;
 while(current!=null){
 if(head.next==null){
 head.next=current;
 break;
 }
 else{
 temp1=head.next;
 head.next=current;
 temp2=current.next;
 current.next=temp1;
 current=temp2;
 head=temp1;
 }
 }
 }
 public static void main(String[] args){
 LinkList list=new LinkList();
 list.insertHead(5);
 list.insertHead(4);
 list.insertHead(3);
 list.insertHead(2);
 list.insertHead(1);
 //list.display();
 //System.out.println();
 relocateList(list.head);
 list.display(); 
 }
}

编辑于 2015-03-13 08:40:34 回复(4)

Java

你为什么不开大

public class Solution {
	/**
	 *	按照左右半区的方式重新组合单链表
	 *	输入：一个单链表的头节点head
	 *	将链表调整成题目要求的样子
	 *
	 *	后台的单链表节点类如下：
	 *
	 public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}
	 */
    public static void relocateList(ListNode head) {
        //1.快慢指针找到中间点
        ListNode hh = new ListNode(-1);//没分清“头部节点”的补救措施
        hh.next = head;
        ListNode l1,lmid,locate;//locate定位节点
        l1 = hh;
        lmid = hh;
        int length = 0;
        for(;l1.next!=null;l1 = l1.next){
            length++;
            if(length%2 == 0)
                lmid = lmid.next;
        }

        if(length > 3) {
            locate = lmid;
            lmid = lmid.next;//lmid及以后的都是R
            locate.next = null;
            l1 = hh.next;

            while (l1 != null) {
                locate = l1;
                l1 = l1.next;
                locate.next = lmid;
                locate = lmid;

                if (l1 != null) {
                    lmid = lmid.next;
                    locate.next = l1;
                }

            }
        }
    }
}

反正过了。。。

发表于 2016-09-23 11:56:06 回复(0)

凯赛尔·麦麦提

我想当个晚上的网管你们可以给我个机会我会好好干的跟客人态度必须100％好的

发表于 2022-04-01 23:07:14 回复(0)

C/C++

冰寒201808102021738

void relocateList(struct ListNode* head) {
if (head == 0 || head->next == 0)

return;

//找到左右链表

    ListNode* newHead = new ListNode(-1);
    newHead->next = head;
    ListNode* slow = newHead;
    ListNode* quick = head;
    while (quick != 0 && quick->next != 0) {
        slow = slow->next;
        quick = quick->next->next;
    }
    ListNode* right = slow->next;
    ListNode* left = head;

slow->next = 0;

//连接

    ListNode *leftCur = 0;
    ListNode *rightCur = 0;
    while (left != 0) {
        leftCur = left;
        left = left->next;
        rightCur = right;
        right = right->next;

        newHead->next = leftCur;
        newHead->next->next = rightCur;
        newHead = newHead->next->next;

    }
    if (right != 0)
        newHead->next = right;
}

发表于 2019-06-03 16:39:43 回复(0)

C/C++

pigff201711160008193

//注意这里的head并不是指带头结点的单链表，这个单链表还是不带头的，head指的是链表的起始节点，一开始搞错了
void relocateList(ListNode* head) {
    //如果链表为空，或者链表只有一个节点，则不动
    if (head == NULL || head->next == NULL)
        return;

    ListNode* cur = head;
    int count = 0;
    //计算不算head的情况下，总共有多少个节点
    while (cur) {
        count++;
        cur = cur->next;
    }

    int mid = count / 2;
    ListNode* leftbegin = head;
    ListNode* rightbegin = head;
    ListNode* leftend = NULL;
    while (mid) {
        if (mid == 1)
            //找到左区间的最后一个节点
            leftend = rightbegin;
        //找到右区间的第一个节点
        rightbegin = rightbegin->next;
        mid--;
    }

    //如果在只有两个节点或者是三个节点的情况下，是不用发生变换的
    if (leftbegin->next == rightbegin)
        return;

    while (1) {
        //完成后半部分指针的变换
        //让tmp等于rightbegjin，并让rightbegin往后走，此时tmp还是之间的rightbegin
        //让leftend的next指向现在的rightbegin，因为，之前的rightbegin即tmp要被插入到前面去
        ListNode* tmp = rightbegin;
        rightbegin = rightbegin->next;
        leftend->next = rightbegin;

        //完成前半部分指针的变换
        //让next等于leftbegin的next（新插入的右区间的节点的next是这个next节点）
        //让leftbegin的next等于新插入的右区间的节点，即tmp
        //让新插入的右区间的节点的next等于原来leftbegin的next，即上面赋值的next节点
        //让leftbegin变为变为左区间的下一个节点，即next节点
        ListNode* next = leftbegin->next;
        leftbegin->next = tmp;
        tmp->next = next;
        leftbegin = next;

        //如果leftbegin此时已经是leftend了，说明左区间只剩一个了
        //那么此时前面全部插入完了，右区间可能剩下一个或两个节点，这个时候根据题目要求就不用改变了，所以直接break
        if (leftbegin == leftend)
            break;
    }
}

发表于 2018-06-10 16:23:00 回复(0)

actlea

题目要说明链表长度包括头节点呀，一直都不知道程序那错了

发表于 2015-04-02 11:07:48 回复(0)

轻水无恒

void relocateList(struct ListNode* head,int N) {

assert(head != NULL);

//我这里直接从4个或者以上节点开始考虑

assert(N >= 4);
ListNode* After;

After = head;

//找到交换的第一个节点

    for (int i = 0; i < N / 2; i++)
    {
        After = After->next;
    }

ListNode* Pre,*Aft;

//开始交换，过程和反转链表一样。

    while (Pre->next != Aft )
    {
        ListNode *PreNext = Pre->next;
        ListNode*AfterNext = After->next;
        Pre->next= After;
        After->next = PreNext;
        After = AfterNext;
        Pre = PreNext;

}

//由于有奇偶的区别，最后一次手动交换，否则会丢掉奇数的最后一个节点

Pre->next = After;
}
};

发表于 2015-04-01 15:39:43 回复(0)

Manfestain

typedef struct node{//定义节点类型
    int data;
    struct node * next;
}node;

void ExchangeList(node *head,int n)//交换函数
{
    node *left,*right,*q,*p;
    int i;
    right=head;q=head->next;
    for(i=1;i<(n/2);i++){//先找到中间结点
        right=q;
        q=q->next;
    }
    printf("right的节点值：%5d\n",right->data);
    printf("q的节点值    ：%5d\n",q->data);
    left=head;p=head->next;
    for(int i=0;i<(n/2)-1;i++){//完成交换
        left->next=q;
        right->next=q->next;
        q->next=p;
        left=p;p=p->next;
        q=right->next;
    }
}

void Print(node *h)//打印函数
{
    for(node *p=h;p;p=p->next){
        printf("%5d",p->data);
    }
    printf("\n");
}

int main(void)
{
    node *p,*tail;
    int n=7;

    node *head=(node *)malloc(sizeof(node));
    head->data=1;
    head->next=NULL;tail=head;
    for(int i=0;i<n-1;i++){
        p=(node *)malloc(sizeof(node));
        p->data=i+2;
        p->next=NULL;
        tail->next=p;tail=p;
    }

    Print(head);
    ExchangeList(head,n);
    printf("The finall answer:");
    Print(head);

    system("pause");
    return 0;
}

发表于 2015-03-28 14:39:16 回复(0)

差二棵树

做的不漂亮

发表于 2015-03-27 10:38:31 回复(0)

wikizhu

自己的编译器不free出错，这里free出错☺

class Solution {
public:
 /**
 *	按照左右半区的方式重新组合单链表
 *	输入：一个单链表的头节点head
 *	将链表调整成题目要求的样子
 *
 *	后台的单链表节点类如下：
 *
 struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
 val(x), next(NULL) {
 }
 };
 */
 void relocateList(struct ListNode* head) {
 int n=0;
        struct ListNode *l1=(struct ListNode *)malloc(sizeof(struct ListNode));
        l1=head;
        while(l1!=NULL){
            n++;
            l1=l1->next;
        }
        l1=head;
        struct ListNode *l2=(struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode *l3=(struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode *l4=(struct ListNode *)malloc(sizeof(struct ListNode));
        l2=l1->next;
        l3=l1;
        int i=1;
        while(i<n/2){
            l3=l3->next;
            i++;
        }
        l4=l3->next;
        
        i=1;
        while(i<n/2){
            l3->next=l4->next;
            l4->next=NULL;
            
            l4->next=l1->next;
            l1->next=l4;
            
            
            l1=l1->next->next;
           
            
            l4=l3->next;
            
            i++;
        }
        //free(l4);
        //free(l3);
        //free(l2);
        //free(l1);
        
    }
};

发表于 2015-03-19 11:49:40 回复(0)