-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
1.输入并查找
方案：头插法，正向查找第m个元素。
import java.util.Scanner; public class Main { /** * @param args */ public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { ListNode node = new ListNode(); node.next = null; int N = in.nextInt(); for (int i = 0; i < N; i++) { ListNode p = new ListNode(); int x = in.nextInt(); p.next = node.next; p.data = x; node.next = p; } int k = in.nextInt(); ListNode kthNode = getKthNode(node,k); System.out.println(kthNode.data); } } public static ListNode getKthNode(ListNode node,int k){ ListNode front = node,behind = node; int x=0; while(front.next!=null && x<=k){ x++; front = front.next; } return front; }} class ListNode { public int data; public ListNode next;} 2.指定单向链表并查找倒数第m个元素
两种情况：无环、有环
无环方案：因为无环单向链表最后一个元素next一定为null，因此设置两个指针slow = head ，fast = head + m，当fast.next == null时slow.next恰好是倒数第m个元素。
有环方案：查找连接点，分割成无环单向链表，最后一个元素next一定为连接点join，将最后一个元素next --> null，此时用无环方案即可解决。因此设置连个指针slow = head ，fast = head + m，当fast.next == null时slow.next恰好是倒数第m个元素。
无环方案Class ：
package limeMianShi.link;public class Test01 { public static void main(String[] args) { ListNode head = new ListNode(0); ListNode p = head; for (int i = 1; i <= 10; i++) { ListNode node = new ListNode(i); p.next = node; p = node; } printListNode(head); printKElement(head,3); } private static void printKElement(ListNode head, int m) { if(m == 0){ System.out.println("null"); } ListNode p = head; if(m > 0){ for(int i = 0;i < m;i++){ if(i == m - 1){ System.out.println("正数第" + m + "个元素为： " + p.data); } p = p.next; } }else{ ListNode s = head; for(int i = 0;i < -m;i++){ p = p.next; } while(null != p){ s = s.next; p = p.next; } System.out.println("倒数第" + (-m) + "个元素为： " + s.data); } } private static void printListNode(ListNode head) { if (null != head) { System.out.print(head.data + " --> "); printListNode(head.next); }else{ System.out.println("null"); } }}class ListNode { public int data; public ListNode next; public ListNode() { super(); } public ListNode(int data) { this.data = data; }} 有环方案Class ：
package limeMianShi.link;public class Test02 { public static void main(String[] args) { ListNode head = new ListNode(0); ListNode p = head; ListNode p4 = null; for (int i = 1; i <= 10; i++) { ListNode node = new ListNode(i); p.next = node; p = node; if (i == 4) { p4 = node; } } p.next = p4; pullLoop(head); printListNode(head); for (int i = 1; i < 11; i++) { printKElement(head, -i); } } private static void printListNode(ListNode head) { if (null != head) { System.out.print(head.data + " --> "); printListNode(head.next); } else { System.out.println("null"); } } private static void printKElement(ListNode head, int m) { if (m == 0) { System.out.println("null"); } ListNode p = head; if (m > 0) { for (int i = 0; i < m; i++) { if (i == m - 1) { System.out.println("正数第" + m + "个元素为： " + p.data); } p = p.next; } } else { ListNode s = head; for (int i = 0; i < -m; i++) { p = p.next; } while (null != p) { s = s.next; p = p.next; } System.out.println("倒数第" + (-m) + "个元素为： " + s.data); } } private static void pullLoop(ListNode head) { ListNode p = getP(head); ListNode pre = null; while (head != p) { pre = p; head = head.next; p = p.next; } pre.next = null; } private static ListNode getP(ListNode head) { ListNode solw = head.next; ListNode fast = head.next.next; while (solw != fast) { solw = solw.next; fast = fast.next.next; } return solw; }}class ListNode { public int data; public ListNode next; public ListNode() { } public ListNode(int data) { this.data = data; }} 啦啦啦