链表

---

请注意：所包含的头文件如下

#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include"LinkList.h"
#include"DLinkedList.h"
#include<stdlib.h>
#include"SqList.h"
#include"preface.h"

题目24

求孪生和： 一个长度为n（n为偶数）的不带头节点的单链表，且结点值都大于0，设计算法求这个单链表的最大孪生和，孪生和定义为第一个结点与其孪生结点之和，对于第i个结点，其孪生结点为第n-i-1个结点

int get_big_sum(LinkList L)
{
	LNode*pre=L->next,*last=L->next;
	while(last)
	{
		pre=pre->next;
		last=last->next->next;
	}//链表长度为偶数，那么last为空时pre就来到了链表的中间位置
	//逆置链表
	LNode*now=NULL;
	while(pre)
	{
		LNode*next=pre->next;
		pre->next=now;
		now=pre;
		pre=next;
	}
	LNode*first=L->next;
	int max=(now->data+first->data);
	while(now)
	{
		if(max<(now->data+first->data))
		{
			max=now->data+first->data;
		}
		first=first->next;
		now=now->next;
	}
	return max;
	
}

注意我只写了带头节点创建链表的方法，但是是按不带头结点的方法进行处理的。

#include "stdafx.h"
int main()
{
	LinkList L;
	initLinkList(L);
	createLinkListBytail(L);
	printLinkList(L);
	
	printf("\nmax=%d\n",get_big_sum(L));
	system("pause");
	return 0;
}

题目25

将链表进行划分，并保持其相对的次序。例如，L={1,5,4,4,2,5,3,2,6,5,3,4}。且target=4
小于目标值的放在左边，大于目标值的放在右边

void divide_linklistL(LinkList &L, int target)
{
	LinkList A,B,C;
	initLinkList(A);
	initLinkList(B);
	initLinkList(C);
	LNode*pre=L,*last=pre->next,*a=A,*b=B,*c=C;
	while(pre->next)
	{
		if(last->data>target)
		{
			pre->next=last->next;
			last->next=a->next;
			a->next=last;
			a=last;
			last=pre->next;
		}else if(last->data<target){
			pre->next=last->next;
			last->next=b->next;
			b->next=last;
			b=last;
			last=pre->next;
		}else{
			pre->next=last->next;
			last->next=c->next;
			c->next=last;
			c=last;
			last=pre->next;
		
		}//保持相对位置不变，用的头插法
	}
	L->next=B->next;
	b->next=C->next;
	c->next=A->next;//将各个链表串起来
	free(A);
	free(B);
	free(C);

}

下面是测试代码：

#include "stdafx.h"
int main()
{
	LinkList L;
	initLinkList(L);
	createLinkListBytail(L);
	printLinkList(L);
	divide_linklistL(L,5);
	printLinkList(L);
	system("pause");
	return 0;
}