/**
*
* @author whc
*
*/
public class LinkedList
{
private static class Node
{
private int data;
private Node next;
public Node()
{
}
public Node(int data,Node next)
{
this.data = data;
this.next = next;
}
}
//向單連結清單中插入結點
public static void insert(Node header,int data,int index)
{
Node pre = getNodeByIndex(header,index-1);//擷取index前向節點
Node newNode = new Node(data, pre.next);//建立新結點，并令其next指向index節點
pre.next = newNode; //index-1節點next指向newNode
}
//删除節點
public static int delete(Node header,int index)
{
Node cur = null;
if(index == 0) //若為頭結點
{
cur = header;
header = header.next;
}
else
{
Node pre = getNodeByIndex(header,index-1);
cur = pre.next;
pre.next = cur.next;
cur.next = null;
}
return cur.data;
}
//O(1)時間複雜度删除節點
public static void quickQelete(Node header,int index)
{
Node delete = getNodeByIndex(header, index);
if(delete.next == null) //若删除的是尾結點，需周遊找到前結點
{
if(header == delete)
header = null;
else
{
Node temp = header;
while(temp.next != delete)
temp = temp.next;
temp.next = null;
}
}
else //狸貓換太子
{
delete.data = delete.next.data;
delete.next = delete.next.next;
}
}
//尋找倒數第k個元素
public static Node getBackward(Node header,int k)
{
Node pre = header;
Node rear = getNodeByIndex(header,k-1);//求倒數第k個結點，兩結點其實相差(k-1)
while(rear.next != null)
{
pre = pre.next;
rear = rear.next;
}
return pre;
}
//單連結清單反轉(非遞歸)
public static Node reverse(Node header)
{
Node pre = header;
Node cur = header.next;
Node rear = null;
while(cur != null)
{
rear = cur.next;
cur.next = pre;
pre = cur;
cur = rear;
}
header.next = null;
header = pre;
return header;
}
//單連結清單反轉(遞歸)
public static Node reverse2(Node header)
{
if(header==null||header.next==null)return header;
Node reHeader=reverse2(header.next);
header.next.next=header;
header.next=null;
return reHeader;
}
//從尾到頭列印單連結清單(遞歸)
public static void printByReverse(Node header)
{
if(header == null)
return;
else
{
printByReverse(header.next);
System.out.print(header.data + ",");
}
}
//合并兩個有序連結清單(非遞歸)
public static Node mergeSorted(Node header1,Node header2)
{
Node header = null;
Node cur = header;
while(header1 != null && header2 != null)
{
if(header1.data <= header2.data)
{
cur.next = header1;
cur = cur.next;
header1 = header1.next;
}
else
{
cur.next = header2;
cur = cur.next;
header2 = header2.next;
}
}
if(header1 != null)
cur.next = header1;
if(header2 != null)
cur.next = header2;
return header;
}
//合并兩個有序的單連結清單(遞歸)
public static Node mergeSortedList(Node header1,Node header2)
{
if(header1 == null)
return header2;
if(header2 == null)
return header1;
Node header = null;
if(header1.data > header2.data)
{
header = header2;
header.next = mergeSortedList(header1, header2.next);
}
else
{
header = header1;
header.next = mergeSortedList(header1.next, header2);
}
return header;
}
//對單連結清單進行歸并排序
public static Node mergeSort(Node header)
{
Node rear = null;
if(header == null || header.next == null)
return header;
else if(header.next.next == null)
{
rear = header.next;
header.next = null;
}
else
{
Node mid = getMidNode(header);
rear = mid.next;
mid.next = null;
}
return mergeSortedList(mergeSort(header),mergeSort(rear));//合并兩個有序連結清單
}
//交換連結清單中任意兩個節點
public static void swap(Node header,Node p,Node q)
{
if(p == header || q == header || p == null || q == null || p == q)
return;
else if(p.next == q)
{
Node pre_p = findPre(header, p);
pre_p.next = q;
p.next = q.next;
q.next = p;
}
else if(q.next == p)
{
Node pre_q = findPre(header, q);
pre_q.next = p;
q.next = p.next;
p.next = q;
}
else
{
Node after_p = p.next;
Node pre_p = findPre(header, p);
Node pre_q = findPre(header, q);
p.next = q.next;
pre_q.next = p;
pre_p.next = q;
q.next = after_p;
}
}
//判斷連結清單中是否有環
public static boolean isCycle(Node header)
{
boolean flag = false;
Node fast = header;
Node slow = fast;
if(fast == null)
return false;
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(fast == slow)
{
flag = true;
break;
}
}
return flag;
}
//判斷兩個連結清單是否相交(無環情況)，并傳回相交的第一個結點。
public static Node isIntersect(Node header1,Node header2)
{
Node target = null;
int len1 = length(header1);
int len2 = length(header2);
if(len1 == 0 || len2 == 0)
return target;
if(len1 > len2)//長連結清單先出發前進二者之差步
{
for(int i = 0;i < len1-len2;i++)
header1 = header1.next;
}
else
{
for(int i = 0;i < len2-len1;i++)
header2 = header2.next;
}
while(header1 != null && header2 != null)
{
if(header1 == header2) //相遇的第一步即為兩連結清單相交的第一個點
{
target = header1;
break;
}
else //二者共同前進
{
header1 = header1.next;
header2 = header2.next;
}
}
return target;
}
//删除連結清單中的重複結點(遞歸)
public static Node deleteSame(Node header)
{
Node temp = header,pointer;
if(header.next == null)
return header;
header.next = deleteSame(header.next);
pointer = header.next;
while(pointer != null)
{
if(header.data == pointer.data)
{
temp.next = pointer.next;
pointer.next = null;
pointer = temp.next;
}
else
{
temp = temp.next;
pointer = pointer.next;
}
}
return header;
}
//擷取連結清單中間結點
public static Node getMidNode(Node header)
{
Node slow = header;
Node fast = slow;
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//擷取結點前驅結點
public static Node findPre(Node header,Node p)
{
Node q = header;
while(q != null)
{
if(q.next == p)
return q;
else
q = q.next;
}
return null;
}
//根據索引擷取結點
public static Node getNodeByIndex(Node header,int index)
{
Node cur = header;
int i;
if(index >= length(header)-1)
return null;
for(i = 0; i < index; i++)
cur = cur.next;
return cur;
}
//周遊連結清單
public static void view(Node header)
{
Node temp = header;
while(temp != null)
{
System.out.print(temp.data + ",");
temp = temp.next;
}
System.out.println();
}
//擷取連結清單長度
public static int length(Node header)
{
int num = 0;
Node cur = header;
while(cur != null)
{
num++;
cur = cur.next;
}
return num;
}
public static void main(String[] args)
{
Node header = null;//頭結點
Node tail = null;//尾結點
int n = 9;
Node cur = null;
while((n--) != 0) //建立一單連結清單
{
int random = (int)(Math.random()*100%20);
if(header == null)
{
header = new Node(random,null);
cur = header;
}
else
{
cur.next = new Node(random, null);
cur = cur.next;
}
}
tail = cur;
System.out.println("建立的單連結清單：");
view(header);//周遊單連結清單
System.out.println("插入[99]結點後：");
insert(header, 99, 5);
view(header);
System.out.println("删除[99]結點後：");
delete(header, 5);
view(header);
System.out.println("倒數第五個結點：" + getBackward(header, 5).data);
// System.out.println("反轉後的單連結清單：");
// view(reverse(header));
System.out.println("從尾到頭列印單連結清單：");
printByReverse(header);
System.out.println("擷取的中間結點為：");
System.out.println(getMidNode(header).data);
// System.out.println("排序之後的單連結清單：");
// Node header2 = mergeSort(header);
// view(header2);
Node Node1 = getNodeByIndex(header, 3);
Node Node2 = getNodeByIndex(header, 4);
swap(header, Node1, Node2);
System.out.println("Node1與Node2交換之後：");
view(header);
System.out.println("判斷單連結清單是否有環：" + isCycle(header));
System.out.println("删除連結清單中重複節點後：");
view(deleteSame(header));
}
}
</pre><pre name="code" class="java">
參考自：http://blog.csdn.net/kerryfish/article/details/24043099
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)