题目描述：给定一个带头结点的单链表，请将其逆序。即如果单链表原来为 head→1→2→3→4→5→6→7，则逆序后变为head→7→6→5→4→3→2→1。
class LNode{
int data; //数据域
LNode next;//下一个节点的引用
}
//方法一：就地逆序 时间复杂度为O(N),空间复杂度为O(1)
public class ListDemo {
public static void Reverse(LNode head){
//判断链表是否为空
if(head==null||head.next==null)
return;
LNode pre=null; //前驱节点
LNode cur=null;//当前节点
LNode next=null;//后继节点
//把链表首节点变为尾节点
cur=head.next;
next=cur.next;
cur.next=null;
pre=cur;
cur=next;
//使当前遍历到的节点cur指向其前驱节点
while (cur.next!=null){
next=cur.next;
cur.next=pre;
pre=cur;
cur=cur.next;
cur=next;
}
//结点最后一个结点指向倒数第二个结点
cur.next=pre;
//链表的头结点指向原来链表的尾结点
head.next=cur;
}
public static void main(String[] args) {
//链表头结点
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
for(int i=0;i<8 ;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
System.out.print("逆序前：");
for(cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
System.out.print("n逆序后：");
Reverse(head);
for(cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
}
}
//递归法 时间复杂度为O(N)
private static LNode RecursiveReverse(LNode head){
//如果链表为空或者链表只有一个元素
if(head==null||head.next==null)
return head;
else{
//反转后面的结点、
LNode newhead=RecursiveReverse(head.next);
//把当前遍历的结点加到后面结点逆序链表的尾部
head.next.next=head;
head.next=null;
return newhead;
}
}
public static void Reverse(LNode head){
if(head==null){
return;
}
//获取链表第一个结点
LNode firstNode=head.next;
//对链表进行逆序
LNode newhave=RecursiveReverse(firstNode);
//头结点指向逆序后链表的第一个结点
head.next=newhave;
}
public void ReversePrint(LNode firstNode){
if(firstNode==null)
return;
ReversePrint(fristNofe.next);
System.out.print(firstNode.data+"")
}
public static void Reverse(LNode head){
//判断链表是否为空
if(head==null||head.next==null)
return;
LNode cur=null;
LNode next=null;
cur=head.next.next;
//设置链表第一个结点为尾结点
head.next.next=null;
//把遍历到结点插入到头结点的后面
while (cur!=null){
next=cur.next;
cur.next=head.next;
cur=next;
}
}
2.如何从无序链表中移除重复
题目描述：
给定一个没有排序的链表，去掉其重复项，并保留原顺序，如链表1→3→1→5→5→7，去掉重复项后变为1→3→5→7。
class LNode{
int data;
LNode next;
}
public class RemoveDemo {
//顺序删除 时间复杂度O(N^2）空间复杂度O（1）
public static void removeDup(LNode head){
if(head==null||head.next==null)
return;
LNode outerCur=head.next; //用于外层循环
LNode innerCur=null; //内层循环用来遍历
LNode innerPre=null;//innerCur的前去结点
for(;outerCur!=null;outerCur=outerCur.next){
for(innerCur=outerCur.next,innerPre=outerCur ;innerCur!=null;){
//找到重复的结点并删除
if(outerCur.data==innerCur.data){
innerPre.next=innerCur.next;
innerCur=innerCur.next;
}else {
innerPre=innerCur;
innerCur=innerCur.next;
}
}
}
}
public static void main(String[] args) {
int i=1;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
for(;i<7;i++){
tmp=new LNode();
if (i%2==0)
tmp.data=i+1;
else if(i%3==0)
tmp.data=i-2;
else
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
System.out.print("删除重复结点前：");
for(cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
removeDup(head);
System.out.print("n删除重复结点后：");
for(cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
}
}
//递归法，效率较低
private static LNode removeDupRecursion(LNode head) {
if (head.next == null)
return head;
LNode pointer = null;
LNode cur = head;
head.next = removeDupRecursion(head.next);
pointer = head.next;
//找同相同的删除
while (pointer != null) {
if (head.data == pointer.data) {
cur.next = pointer.next;
pointer = cur.next;
} else {
pointer = pointer.next;
cur = cur.next;
}
}
return head;
}
public static void removeDup(LNode head){
if(head==null)
return;
head.next=removeDupRecursion(head.next);
}
3.如何计算两个单链表所代表的数之和
题目描述：
给定两个单链表，链表的每个结点代表一位数，计算两个数的和。例如，输入链表（3→1→5）和链表（5→9→2），输出：8→0→8，即513+295=808，注意个位数在链表头。
class LNode {
int data;
LNode next;
}
public class AddDemo {
//链表相加
public static LNode add(LNode h1, LNode h2){
if(h1==null||h1.next==null)
return h2;
if(h2==null||h2.next==null)
return h1;
int c=0; //记录进位
int sum=0; //记录和
LNode p1=h1.next; //遍历h1
LNode p2=h2.next;//遍历h2
LNode tmp=null;//新创建的存储相加和的结点
LNode resultHead=new LNode();
resultHead.next=null;
LNode p=resultHead;
while (p!=null&&p2!=null){
tmp=new LNode();
tmp.next=null;
sum=p1.data+ p2.data+c;
tmp.data=sum%10;
p.next=tmp;
p=tmp;
p1=p1.next;
p2=p2.next;
}
//h2比h1长
if(p1==null){
while (p2!=null){
tmp=new LNode();
tmp.next=null;
sum=p2.data+c;
tmp.data=sum%10;
c=sum/10;
p.next=tmp;
p=tmp;
p2=p2.next;
}
}
//h1比h2长
if(p2==null){
while (p1!=null){
tmp=new LNode();
tmp.next=null;
sum=p1.data+c;
tmp.data=sum%10;
c=sum/10;
p.next=tmp;
p=tmp;
p1=p1.next;
}
}
//是否需要进位
if(c==1){
tmp=new LNode();
tmp.next=null;
tmp.data=1;
p.next=tmp;
}
return resultHead;
}
public static void main(String[] args) {
int i=1;
LNode head1=new LNode();
head1.next=null;
LNode head2=new LNode();
head2.next=null;
LNode tmp=null;
LNode cur=head1;
LNode addResult=null;
//构造链表
for(; i<7;i++) {
tmp = new LNode();
tmp.data = i + 2;
tmp.next = null;
cur.next = tmp;
cur = tmp;
}
cur=head2;
//构造第二个链表
for(i=9;i>4;i--){
tmp=new LNode();
tmp.data=i+2;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
System.out.print("Head1:");
for(cur=head1.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
System.out.print("n Head2:");
for(cur=head2.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
addResult=add(head1,head2);
System.out.print("n相加后：");
for(cur=addResult.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
}
}
4.如何对链表进行重新排序
题目描述：给定链表L0→L1→L2→…→Ln-1→Ln，把链表重新排序为L0→Ln→L1→Ln-1→L2→Ln-2→…。要求：①在原来链表的基础上进行排序，即不能申请新的结点；②只能修改结点的next域，不能修改数据域。
class LNode {
int data; //数据域
LNode next;//下一个节点的引用
}
public class softDemo {
//找出链表中间结点
private static LNode FinddleNode(LNode head) {
if (head == null || head.next == null)
return head;
LNode fast = head;//遍历时每次向前走两步
LNode slow = head;//遍历时每次向前走一步
LNode slowPre = head;
//当fast到链表尾时，slow恰好指向链表的中间结点
while (fast != null && fast.next != null) {
slowPre = slow;
slow = slow.next;
fast = fast.next.next;
}
//把链表断开两个独立的子链表
slowPre.next = null;
return slow;
}
//对不带头结点的单链表翻转 翻转
private static LNode Reverse(LNode head) {
if (head == null || head.next == null)
return head;
LNode pre = head; //前驱结点
LNode cur = head.next;//当前结点
LNode next;//后继结点
pre.next = null;
//使当前结点指向前驱结点
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = cur.next;
cur = next;
}
return pre;
}
//对链表进行排序
public static void Reorder(LNode head) {
if (head == null || head.next == null)
return;
//前半部分链表第一个结点
LNode cur1 = head.next;
LNode mid = FinddleNode(head.next);
//后半部分链表逆序的第一个结点
LNode cur2 = Reverse(mid);
LNode tmp = null;
//合并两个链表
while (cur1.next != null) {
tmp = cur1.next;
cur1.next = cur2;
cur1 = tmp;
tmp = cur2.next;
cur2.next = cur1;
cur2 = tmp;
}
cur1.next = cur2;
}
public static void main(String[] args) {
int i = 1;
LNode head = new LNode();
head.next = null;
LNode tmp = null;
LNode cur = head;
//构造第一个链表
for (; i < 8; i++) {
tmp = new LNode();
tmp.data = i;
tmp.next = null;
cur.next = tmp;
cur = tmp;
}
System.out.print("排序前： ");
for (cur = head.next; cur != null; cur = cur.next)
System.out.print(cur.data + " ");
Reorder(head);
System.out.print("n排序后");
for (cur = head.next; cur != null; cur = cur.next)
System.out.print(cur.data + " ");
}
}
5.如何快速找出链表中的倒数第k个元素
题目描述：
找出单链表中的倒数第k个元素，如给定单链表：1→2→3→4→5→6→7，则单链表的倒数第k=3个元素为5。
class LNode {
int data;
LNode next;
}
//快慢指针法
public class ReciprocalListDemo {
//构造一个单链表
public static LNode ConstructList() {
int i=1;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
//构造第一个链表
for(;i<8;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
return head;
}
//顺序打印单链结点的数据
public static void PrintList(LNode head){
for(LNode cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
}
//找出链表倒数第k个结点
public static LNode FindLast(LNode head ,int k){
if(head==null||head.next==null)
return head;
LNode slow ,fast;
slow=fast=head.next;
int i;
for(i=0;i
6.如何将单链表向右旋转k个位置
题目描述：
给定单链表1→2→3→4→5→6→7，k=3，那么旋转后的单链表变为5→6→7→1→2→3→4。
class LNode {
int data;
LNode next;
}
public class RightRotationListDemo {
//链表旋转k个位置
public static void Rotation(LNode head, int k) {
if (head == null || head.next == null)
return;
//fast表示先走k步,然后与slow指针同时向后走
LNode slow, fast, tmp;
slow = fast = head.next;
int i;
for (i = 0; i < k && fast != null; ++i) {//前移k步
fast = fast.next;
}
//判断k 是否超出链表长度
if (i < k)
return;
//循环结束后slow指向链表倒数第k+1个元素，fast指向链表最后一个元素
while (fast.next!=null){
slow=slow.next;
fast=fast.next;
}
tmp=slow;
slow=slow.next;
tmp.next=null;
fast.next=head.next;
head.next=slow;
}
public static LNode ConstructList(){
int i=1;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
//构造第一个链表
for(;i<8;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
return head;
}
//循环打印单链表结点的数据
public static void PrintList(LNode head){
for (LNode cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
}
public static void main(String[] args) {
LNode head=ConstructList();
System.out.print("旋转前：");
PrintList(head);
Rotation(head,3);
System.out.print("n旋转后：");
PrintList(head);
}
}
7.如果链表存在环，那么如何找出环的入口点？
题目描述：
单链表有环指的是单链表中某个结点的next域指向链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。
class LNode {
int data;
LNode next;
}
public class LoopEntryListDemo {
//构造链表
public static LNode constructList(){
int i=1;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
//构造第一个链表
for(;i<8;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
cur.next=head.next.next.next;
return head;
}
//判断单链表是否有环
public static LNode isLoop(LNode head){
if(head==null||head.next==null)
return null;
//初始slow与fast都指向链表第一个结点
LNode slow=head.next;
LNode fast=head.next;
while (fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
return slow;
}
return null;
}
//环入口
public static LNode findLoopNode(LNode head,LNode meetNode){
LNode first=head.next;
LNode second=meetNode;
while (first!=second){
first=first.next;
second=second.next;
}
return first;
}
public static void main(String[] args) {
LNode head=constructList();
LNode meedNode=isLoop(head);
LNode loopNode=null;
if(meedNode!=null){
System.out.println("有环");
loopNode=findLoopNode(head,meedNode);
System.out.println("环的入口为："+loopNode.data);
}else {
System.out.println("无环");
}
}
}
8.如何把链表相邻元素翻转
题目描述：
把链表相邻元素翻转，如给定链表为1→2→3→4→5→6→7，则翻转后的链表变为2→1→4→3→6→5→7。
class LNode {
int data;
LNode next;
}
public class AdjoinReversListDemo {
//相邻元素翻转
public static void reverse(LNode head){
if(head==null||head.next==null)
return;
LNode cur=head.next;
LNode pre=head;
LNode next=null;
while (cur!=null&&cur.next!=null){
next=cur.next.next;
pre.next=cur.next;
cur.next.next=cur;
cur.next=next;
pre=cur;
cur=next;
}
}
public static void main(String[] args) {
int i=1;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
for(;i<8;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
System.out.print("顺序输出：");
for(cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
reverse(head);
System.out.print("n逆序输出：");
for(cur=head.next;cur!=null;cur=cur.next)
System.out.print(cur.data+" ");
for(cur=head.next;cur!=null;){
cur=cur.next;
}
}
}
9.如何把链表以K个结点为一组进行翻转
题目描述：K链表翻转是指把每K个相邻的结点看成一组进行翻转，如果剩余结点不足K个，则保持不变。假设给定链表1→2→3→4→5→6→7和一个数K，如果K的值为2，那么翻转后的链表为2→1→4→3→6→5→7。如果K的值为3，那么翻转后的链表为3→2→1→6→5→4→7。
class LNode {
int data;
LNode next;
}
public class GroupReverse {
//对不带头结点的单链表翻转
private static LNode Reverse(LNode head) {
if (head == null || head.next == null)
return head;
LNode pre = head;
LNode cur = head.next;
LNode next = cur.next;
pre.next = next;
//使当前遍历的结点cur指向其前驱结点
while (cur!=null){
next=cur.next;
cur.next=pre;
pre=cur;
cur=cur.next;
cur=next;
}
return pre;
}
//k翻转
public static void ReverseK(LNode head,int k){
if(head==null||head.next==null)
return;
int i=1;
LNode pre=head;
LNode begin=head.next;
LNode end=null;
LNode pNext=null;
while (begin!=null){
end=begin;
//从begin开始第K个结点
for(;i
10. 如何在只给定单链表中某个结点的指针的情况下删除该结点
题目描述：
假设给定链表1→2→3→4→5→6→7中指向第5个元素的指针，要求把结点5删掉，删除后链表变为1→2→3→4→6→7。
class LNode {
int data;
LNode next;
}
public class RemoveListDemo {
public static void printList(LNode head){
for(LNode cur=head.next;cur!=null;cur=cur.next){
System.out.print(cur.data+" ");
}
}
//判断是否删除指定位置结点
public static boolean RemoveNode(LNode p){
if(p==null||p.next==null)
return false;
p.data=p.next.data;
LNode tmp=p.next;
p.next=tmp.next;
return true;
}
public static void main(String[] args) {
int i=1;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
LNode p=null;
//构造链表
for(;i<8;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
if(i==5)
p=tmp;
}
System.out.print("删除结点"+p.data+"前链表：");
printList(head);
boolean result=RemoveNode(p);
if(result){
System.out.print("n删除后该结点链表:");
printList(head);
}
}
}
11.如何合并两个有序链表
题目描述：
已知两个链表 head1 和 head2 各自有序（如升序排列），请把它们合并成一个链表，要求合并后的链表依然有序。
class LNode {
int data;
LNode next;
}
public class RombineListDemo {
//构造链表
public static LNode ConstructList(int start){
int i=start;
LNode head=new LNode();
head.next=null;
LNode tmp=null;
LNode cur=head;
for(;i<7;i+=2){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
return head;
}
//遍历
public static void PrintList(LNode head){
for(LNode cur=head.next;cur!=null;cur=cur.next){
System.out.print(cur.data+" ");
}
}
//合并两个升序排列的单列表
public static LNode Merge(LNode head1,LNode head2){
if(head1==null||head1.next==null)
return head2;
if(head2==null||head2.next==null)
return head1;
LNode cur1=head1.next;
LNode cur2=head2.next;
LNode head=null;
LNode cur=null;
if(cur1.data> cur2.data){
head=head2;
cur=cur2;
cur2=cur2.next;
}else {
head=head1;
cur=cur1;
cur1=cur1.next;
}
//每次找到链表剩余的最小值对应的结点连接合并后链表的尾部
while (cur1!=null&&cur2!=null){
if(cur1.data< cur2.data){
cur.next=cur1;
cur=cur1;
cur1=cur1.next;
}else {
cur.next=cur2;
cur=cur2;
cur2=cur2.next;
}
}
//遍历完一个链表后把另一个链表剩余的结点连接合并后的链表后面
if(cur1!=null){
cur.next=cur1;
}
if(cur2!=null){
cur.next=cur2;
}
return head;
}
public static void main(String[] args) {
LNode head1=ConstructList(1);
LNode head2=ConstructList(2);
System.out.print("head1:");
PrintList(head1);
System.out.print("nhead2:");
PrintList(head2);
System.out.print("n合并后的链表:");
LNode head=Merge(head1,head2);
PrintList(head);
}
}
12.如何判断两个单链表（无环）是否相交
题目描述：
单链表相交指的是两个链表存在完全重合的部分
class LNode {
int data;
LNode next;
}
public class IntersectListDemo {
//如果两个链表相交，找出相交部分
public static LNode IsIntersect(LNode head1,LNode head2){
if(head1==null||head1.next==null||head2==null||head2.next==null)
return null;
LNode tmp1=head1.next;
LNode tmp2=head2.next;
int n1=0,n2=0;
//遍历head1找出尾结点，同时记录head1的长度
while (tmp1.next!=null){
tmp1=tmp1.next;
++n1;
}
//遍历head2，找出尾结点，同时记录head2的长度
while (tmp2.next!=null){
tmp2=tmp2.next;
++n2;
}
//head1和head2有相同的尾结点
if(tmp1==tmp2){
//长链表先走n1-n2步
if(n1>n2 )
while (n1-n2>0){
head1=head1.next;
--n1;
}
if (n2>n1)
while (n2-n1>0){
head2=head2.next;
--n2;
}
//两个链表同时前进，找出相同的结点
while (head1!=head2){
head1=head1.next;
head2=head2.next;
}
return head1;
}
//没有相同的结点
else
return null;
}
public static void main(String[] args) {
int i=1;
LNode head1=new LNode();
head1.next=null;
LNode head2=new LNode();
head2.next=null;
LNode tmp=null;
LNode cur=head1;
LNode p=null;
for(;i<8;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
if(i==5)
p=tmp;
}
cur=head2;
for(;i<5;i++){
tmp=new LNode();
tmp.data=i;
tmp.next=null;
cur.next=tmp;
cur=tmp;
}
//使他们相交于结点5
cur.next=p;
LNode interNode=IsIntersect(head1,head2);
if(interNode==null){
System.out.println("这两个链表不相交：");
}else {
System.out.println("这两个链表相交点为："+interNode.data);
}
}
}
13.如何展开链接列表
题目描述：
给定一个有序链表，其中每个结点也表示一个有序链表，结点包含两个类型的指针：1）指向主链表中下一个结点的指针（在下面的代码中称为“正确”指针）。2）指向此结点头的链表（在下面的代码中称之为“down”指针）。
public class MergeList {
//链表结点
private class Node{
int data;
Node right,down;
public Node(int daa) {
this.data = daa;
this.right = right;
this.down = down;
}
}
private Node head;
//合并两个有序链表
private Node merge(Node a,Node b){
if(a==null)
return b;
if(b==null)
return a;
//把两个链表头中较小的结点赋值给result
Node result;
if(a.data< b.data){
result=a;
result.down=merge(a.down,b);
}else {
result=b;
result.down=merge(a,b.down);
}
return result;
}
//把链表扁平化处理
public Node flatten(Node root){
if(root==null||root.right==null)
return root;
//递归处理root.right链表
root.right=flatten(root.right);
//把root结点对应的链表与右边链表合并
root=merge(root,root.right);
return root;
}
//把data插入到链表头
private Node insert(Node head_ref ,int data){
Node new_node=new Node(data);
new_node.down=head_ref;
head_ref=new_node;
//返回新的表头结点
return head_ref;
}
public void printList(){
Node temp=head;
while (temp!=null){
System.out.print(temp.data+" ");
temp=temp.down;
}
System.out.println();
}
public static void main(String[] args) {
MergeList L=new MergeList();
//构造链表
L.head=L.insert(L.head,31);
L.head=L.insert(L.head,8);
L.head=L.insert(L.head,6);
L.head=L.insert(L.head,3);
L.head.right= L.insert(L.head.right,21);
L.head.right= L.insert(L.head.right,11);
L.head.right.right= L.insert(L.head.right.right,50);
L.head.right.right= L.insert(L.head.right.right,22);
L.head.right.right= L.insert(L.head.right.right,15);
L.head.right.right.right= L.insert(L.head.right.right.right,55);
L.head.right.right.right= L.insert(L.head.right.right.right,40);
L.head.right.right.right= L.insert(L.head.right.right.right,39);
L.head.right.right.right= L.insert(L.head.right.right.right,30);
//扁平化链表
L.head=L.flatten(L.head);
L.printList();
}
}
