代码依旧用c#的写的增加了修改删除合并的方法，我会坚持写下去,如有不对 之处希望大家斧正，注释写的比较详细。有什么问题欢迎留言。
链表节点类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 线性表ccc
{
public class MyLinkListNode<T>
{
public MyLinkListNode()
{
}
public T data;
public MyLinkListNode(T data)
{
this.data = data;
}
//下一个节点
public MyLinkListNode<T> next;
}
}
链表类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 线性表ccc
{
public class MyLinkList<T>
{
//链表长度
private int count;
public int Count
{
get { return count; }
}
//链表头
MyLinkListNode<T> head;
public MyLinkList()
{
head = new MyLinkListNode<T>();
head.next = null;
}
public MyLinkList(T[] nums):this()
{
AddItem(nums);
}
/// <summary>
/// 增加一组数组到链表里
/// </summary>
/// <param name="nums"></param>
private void AddItem(T[] nums)
{
foreach (T item in nums)
{
AddObject(item);
}
}
/// <summary>
/// 把一个节点加到头节点后面
/// </summary>
/// <param name="item"></param>
private void AddObject(T item)
{
//这里给单链表开辟了表长的空间
MyLinkListNode<T> p = new MyLinkListNode<T>();
p.data = item;
//设置原来的父节点的子节点为 现子节点的父节点
p.next = head.next;
//建立头节点与子节点的关系
head.next = p;
count++;
}
/// <summary>
/// 获取链表某个位置的元素
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetElem(int index)
{
MyLinkListNode<T> p = head.next;
int j = 0;
while(p!=null&&index>j)
{
p = p.next;
j++;
}
if (p==null||j>index)
{
throw new Exception("超出界限");
}
return p.data;
}
/// <summary>
/// 向链表插入一个元素
/// </summary>
/// <param name="index"></param>
/// <param name="elem"></param>
/// <returns></returns>
public void InsertElem(int index,T elem)
{
MyLinkListNode<T> p = head;
int j = 0;
if (index>=count)
{
throw new Exception("插入的索引超界");
}
while (p != null&&index>j)
{
p = p.next;
j++;
}
MyLinkListNode<T> newnode = new MyLinkListNode<T>(elem);
//让它指向原来上一个节点指向的元素
newnode.next = p.next;
//让老节点指向插入的新节点
p.next = newnode;
count++;
}
/// <summary>
/// 删除一个元素
/// </summary>
public void DeleteElem(int index)
{
//把头节点赋值给一个临时节点
MyLinkListNode<T> p = head;
int j = 0;
// =的情况也不行因为链表最多取到count - 1
if (index > count)
{
throw new Exception("删除的索引超界");
}
//取到删除节点的上一个节点
while (p != null&&index > j)
{
p = p.next;
j++;
}
//删除P.next让p.next指向p.next的next; 此时原来的p.next没有引用会被GC自动销毁
p.next = p.next.next;
//删除之后count要-1
count--;
//GC.Collect();
}
/// <summary>
/// 修改链表index位置的值
/// </summary>
/// <param name="index"></param>
/// <param name="elem"></param>
public void UpDateElem(int index,T elem)
{
MyLinkListNode<T> p = head;
// =的情况也不行因为链表最多取到count - 1
if (index >= count)
{
throw new Exception("删除的索引超界");
}
int j = 0;
//定位要要修改的位置
while (index >= j)
{
p = p.next;
j++;
}
p.data = elem;
}
/// <summary>
/// 把La和Lb归并成一个单链表,由于不知道类型传一个回调函数进来
/// </summary>T
/// <param name="ListA"></param>
/// <param name="ListB"></param>
/// <returns></returns>
public MyLinkList<T> MergeList(MyLinkList<T> La,Func<T,T,bool> func)
{
MyLinkList<T> Lc = new MyLinkList<T>();
Lc.count = La.count + count;
MyLinkListNode<T> pa, pb, pc;
pb = La.head.next;
pa = this.head.next;
//Lc.head和pc指向同一片空间
pc = Lc.head;
while (pa != null && pb!=null)
{
//如果pa<=pb
if (func(pa.data,pb.data))
{
pc.next = pa;
//让pc指针前移
pc = pa;
//pa的指针前移
pa = pa.next;
}
else
{
pc.next = pb;
pc = pb;
pb = pb.next;
}
}
if (pb != null)
{
//1次就Pb后面链着的都归了pc
pc.next = pb;
//这时候pc的指针也得前移
pc = pc.next;
}
else
{
pc.next = pa;
pc = pc.next;
}
return Lc;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
MyLinkListNode<T> p = head.next;
while (p != null)
{
sb.Append(p.data + " ");
p = p.next;
}
return sb.ToString();
}
}
}
实际上操作 都是引用的各种变换 。
测试代码：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 线性表ccc
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("请输入测试数组类似5 4 3");
string[] s = Console.ReadLine().Split(‘ ‘);
int[] nums = new int[s.Length];
for (int i = 0; i < s.Length; i++)
{
nums[i] = Convert.ToInt32(s[i]);
}
//初始化的时候存的类似于 3=>4=>5
MyLinkList<int> ml = new MyLinkList<int>(nums);
Console.WriteLine("链表输出的结果是");
Console.WriteLine(ml.ToString());
while (true)
{
Console.WriteLine("请输入插入的位置");
int indexInsert = int.Parse(Console.ReadLine());
Console.WriteLine("请输入插入的值");
int value = int.Parse(Console.ReadLine());
ml.InsertElem(indexInsert, value);
Console.WriteLine("打印链表结果");
Console.WriteLine(ml.ToString());
Console.WriteLine("请输入要删除的索引");
int indexDel = int.Parse(Console.ReadLine());
ml.DeleteElem(indexDel);
Console.WriteLine(ml.ToString());
Console.WriteLine("请输入要修改的索引");
int indexUpdate = int.Parse(Console.ReadLine());
Console.WriteLine("请输入要修改的值");
int valueUpdate = int.Parse(Console.ReadLine());
ml.UpDateElem(indexUpdate, valueUpdate);
Console.WriteLine("打印链表结果");
Console.WriteLine(ml.ToString());
Console.WriteLine("请输入链表B类似5 4 3");
string[] sB = Console.ReadLine().Split(‘ ‘);
int[] numsB = new int[sB.Length];
for (int i = 0; i < s.Length; i++)
{
numsB[i] = Convert.ToInt32(sB[i]);
}
MyLinkList<int> mlB = new MyLinkList<int>(numsB);
MyLinkList<int> mlC = ml.MergeList(mlB, (x,y)=>x<=y);
Console.WriteLine("合并两个链表的结果是");
Console.WriteLine(mlC.ToString());
Console.WriteLine();
}
}
}
}
结果如图:
算法分析:
删除要找到 删除节点的前一个节点 故一次循环时间复杂度是O(n)
修改也要找到删除节点 时间复杂度也是O(n)
合并操作一共循环m+n次 时间复杂度是O(m+n) 即O(n)
最后更正一下上一篇的一个错误 遍历的时间复杂度是O(n) 不需要循环GetElem详细代码 请参考 这篇里MyLinkList 重载的ToString()方法