Java实现单链表部分翻转
程序员文章站
2022-06-22 23:51:08
...
之前看到了用C语言写的单链表部分翻转的代码,因为现在在学Java,就试着用Java实现,总共包括三个类,节点类Node, 链表类LinkList,测试类NodeList,废话不多说,直接上代码。(从第m个位置到第n个位置翻转)
思路:首先空转,找到开始翻转的第一个节点的前驱,记作head;
以head为起始节点遍历遍历n-m次,第i次时,将找到的节点插入到head 的next中即可。
1<m<=n
节点类:
public class Node {
protected Node next;//指针域
protected int data; //数据域
public Node(int data)
{
this.data=data;
}
public Node getNext()
{
return next;
}
public void display()
{
System.out.print(data+" ");
}
}
链表类:
public class LinkList {
public Node first=null;//头结点
private int pos=0;
public LinkList()
{
this.first=null;
}
public Node deleteFirstNode()
{
Node temp=first;
first=temp.next;
return temp;
}
public Node getNodeByIndex(int index)
{
Node current=first;
while(pos!=index)
{
current=current.next;
pos++;
}
return current;
}
public void addNode(int data)
{
Node node=new Node(data);
if(first==null)
{
first=node;
return;
}
Node temp=first;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=node;
}
public Node deleteNodeByPos(int index)
{
Node current=first;
Node previous=first;
while(pos!=index)
{
previous=current;
current=current.next;
pos++;
}
if(current == first) {
first = first. next;
} else {
pos = 0;
previous. next = current. next;
}
return current;
}
public Node deleteNodeByData(int data)
{
Node previous=first;
Node current=first;
while(current.data!=data)
{
if(current.next==null)
{
return null;
}
else
{
previous=current;
current=current.next;
}
}
if(current==first)
{
first=first.next;
}
else
{
previous.next=current.next;
}
return current;
}
public void displayAllData()
{
Node current=first;
while(current!=null)
{
current.display();
current=current.next;
}
System.out.println();
}
public Node getFirstNode()
{
if(first!=null)
return first;
else
return null;
}
public int getLength()
{
Node current=first;
int length=0;
while(current!=null)
{
current=current.next;
length++;
}
return length;
}
//from开始翻转的位置,to翻转的最后一个位置
public void reverse(Node head,int from,int to)
{
Node pCur=head.next;
int i;
//找到开始翻转的位置的前一个节点
for(i=0;i<from-1;i++)
{
head=pCur;
pCur=pCur.next;
}
Node pPre=pCur;
pCur=pCur.next;
to--;
Node pNext;
for(;i<to;i++)
{
pNext=pCur.next;
pCur.next=head.next;
head.next=pCur;
pPre.next=pNext;
pCur=pNext;
}
}
测试类
import java.io.*;
import java.util.Random;
public class NodeList {
public static void main(String []args) throws IOException
{
LinkList linklist1=new LinkList();
Node head=new Node(0);
for(int i=0;i<10;i++)
{
linklist1.addNode(new Random().nextInt(100));
}
head.next=linklist1.getFirstNode();
linklist1.displayAllData();
linklist1.reverse(head, 2, 3);
linklist1.displayAllData();
}
}