链表的逆置给定一个单链表，实现链表的逆置功能 思路：
在前面的单链表练习中，讲到了头插，头插的链表和正常的序列是刚好相反的，利用这点来进行链表的逆置 代码讲解：
使用cur指针指向第一个数据域，把head单独拿出来，重新对head头插一次，在头插中，cur的next域要先把head的next域接过来，然后把head的next置为cur，这样做的话会丢失cur后面的所有未插入节点，就要使用一个指针next来进行记录,然后cur从next中拿值，不断的更新next。 private void reverse() { Entry cur = head.next; Entry next = null; //开始插入第一个，先把head的next置为空 head.next = null; while (cur != null) { //更新next，next用来保存cur后面的未插入的指针 next = cur.next; //头插 cur.next = head.next; head.next = cur; //更新cur cur = next; } }合并两个有序的链表 给定两个有序的链表，写一个函数实现合并两个链表的功能，而且合并后的链表是有序的。 思路：
使用归并的思想，两个指针分别指向两个链表，哪个指针所指的节点数据域小，那么就把该节点连接到合并后的序列上 代码讲解：
首先明确该方法是链表类的一个方法，所以第一条链表就是本身的head，第二条链表是传进来的list2，分别用两个指针指向单链表，last指向head意思是把list2链表合并到list1上面，所以合并后的序列是last，然后在p和q都没有到最后的情况下，哪个小就接入到last后面，跳出循环后，哪个链表有剩余直接插入到last后面。 
这里的两个链表都有4，但是我比较的条件是
所以会更改路径，先连接q的4，这块可以写成<=
代码实现： public void merge(MiNiLinkedListTest list2) { //用p，q分别引用两个单链表 Entry p = head.next; Entry q = list2.getHead().next; //使用last指针来进行归并这两个指针 Entry last = head; last.next = null; //两个链表都有节点 while(p!=null && q!=null) { //谁小接到last的后面 if(p.data > q.data){ last.next = q; q = q.next; last = last.next; } else { last.next = p; p = p.next; last = last.next; } } //list1还有剩余节点 if(p != null) { last.next = p; } //list2还有剩余节点 if(q != null) { last.next = q; } //已经把list2全部加到了list1上面，list2直接把head的next置为空 list2.getHead().next = null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
判断链表是否有环给定一个链表，判断链表是否有环 思路：
采用快慢指针进行判断，道理很简单，圆形操场跑步，跑的快的人总会追上跑得慢的人，也就是套圈。 给一个有环的例子：
这里从67到78就构成了一个环，来构造一下这个链表，正常的插入肯定是不会出现这种情况的，所以链表的插入就需要我们自己来构造，要自己来设定下一个节点就需要打开private，可以在外部修改链表 这里直接给出构造的代码，方便读者进行测试 MiNiLinkedListTest list1 = new MiNiLinkedListTest(); Entry head = list1.getHead(); Entry node1 = new Entry(34,null); head.next = node1; Entry node2 = new Entry(21,null); node1.next = node2; Entry node3 = new Entry(67,null); node2.next = node3; Entry node4 = new Entry(42,null); node3.next = node4; Entry node5 = new Entry(12,null); node4.next = node5; Entry node6 = new Entry(78,null); node5.next = node6; node6.next = node3;代码讲解：
代码的实现是比较简单的，定义快指针和慢指针同时指向第一个数据节点，然后在不为空的情况下，两个指针开始走，一个走两步，一个走一步，如果再次相遇，则证明链表是有环的，如果有其中一个为空，那么就说明链表是可以走完的，那么就没有环。 private boolean isLoop() { //定义快慢指针 Entry fast = head.next; Entry slow = head.next; while(fast != null && slow != null && fast.next != null) { //快指针每次走两步，慢指针每次走一步 fast = fast.next.next; slow = slow.next; if(fast == slow) { //如果再次相遇，则说明有环，返回true return true; } } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
求链表环的入口节点是上一个问题的延伸，当链表有环时返回链表的入口节点 还是用上一个题的例子来说，我们首先来做一个分析，搞清楚如何去求链表的入口节点。
如图所示，为这几段距离定义了一写变量 x：第一个数据节点到环入口的距离
m：环入口到相遇之间的距离
n：相遇节点到环末尾之间的距离
规律：由于fast每次走2步，slow每次走1步，所以fast的路程是slow路程的2倍 通过上面一起来进行一系列的推导： fast走过的路程是：x+m+n+m slow走过的路程是：x+m 故可得：x+m+n+m = 2 * (x+m) x+n+2m = 2x+2m x = n所以最终得出来的结论是x=n 所以我们只需要定义一个指针从第一个数据开始，一个指针从相遇的节点开始，两个节点同时开始，每次同时走一步，相遇的时候就是环的入口节点。 代码实现： private Integer getLoopHead() { //定义快慢指针 Entry fast = head.next; Entry slow = head.next; while(fast != null && slow != null && fast.next != null) { //快指针每次走两步，慢指针每次走一步 fast = fast.next.next; slow = slow.next; if(fast == slow) { //如果再次相遇，则说明有环 //定义一个指针指向第一个数据节点 Entry cur = head.next; //cur和slow（fast）同时走，相遇时就是入口节点 while(true) { cur = cur.next; slow = slow.next; if(cur == slow) { return cur.data; } } } } return null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
判断两条链表是否相交给定两条链表，判断两条链表是否相交 先来通过一张图来直观的看一下链表的相交 
可以看到 list1 有5个数据节点， list2 有4个数据节点，如何找到相交的那个节点或者说如何判断是否相交呢？
思路：
首先先分别统计两个链表的长度，求出两个链表的差值，然后再重新开始遍历，让长的链表的指针先走两个链表的长度差值，然后两个指针开始同时走，每走一步判断一次是否是同一个节点
具体到这个图中，定义两个指针，分别指向 list1 和 list2，让 list1 先走1步，然后 list1 和 list2 同时开始走，每走一步判断一次，走两步后到6这两个指针就会相交。 为了大家的测试方便，这里先给出构造相交链表的代码： MiNiLinkedListTest list1 = new MiNiLinkedListTest(); MiNiLinkedListTest list2 = new MiNiLinkedListTest(); Entry node1 = new Entry(1, null); Entry node2 = new Entry(2, null); Entry node3 = new Entry(3, null); Entry node4 = new Entry(4, null); Entry node5 = new Entry(5, null); Entry node6 = new Entry(6, null); Entry node7 = new Entry(7, null); list1.head = node1; node1.next = node2; node2.next = node3; node3.next = node6; node6.next = node7; list2.head = node4; node4.next = node5; node5.next = node6;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
代码实现： public boolean isCross(MiNiLinkedListTest list2) { //统计两个链表的长度 int size1 = 0; int size2 = 0; //统计list1 Entry cur = head; while(cur != null) { cur = cur.next; size1++; } //统计list2 cur = list2.head; while(cur != null) { cur = cur.next; size2++; } //为两条链表定义指针 Entry p = head.next; Entry q = list2.head.next; //判断哪条链表长 if(size1 > size2) { int cnt = size1 - size2; while (cnt-- > 0) { p = p.next; } } else if(size1 < size2) { int cnt = size2 - size1; while (cnt-- > 0) { q = q.next; } } //开始同时遍历 while(p != null && q != null) { if(p == q) { return true; } p = p.next; q = q.next; } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
找链表的倒数第k个节点
思路：
如果只定义一个指针也是可以的，但是很明显需要遍历两遍，第一遍找到链表的总长度，第二遍从头开始走总长度-k个位置即可。
如果只遍历一遍，那么可以定义两个指针，如图，开始时，先让lastK指针指向第一个节点，last指针走正数k个位置，然后两个指针同时开始走，当last走到末尾的时候，lastK就是倒数第k个节点。 代码实现： public int lastOrder(int k) { //定义两个指针 Entry lastK = head.next; Entry last = head; //last先走k个位置 while(k-- > 0) { last = last.next; if(last == null) { throw new IllegalArgumentException('超过范围的 k ：'+ k); } } //两个指针同时走 while(last.next != null) { last = last.next; lastK = lastK.next; } return lastK.data; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
链表实现大数的加法**这种算是链表的一种应用，其实实现起来比较的简单，只需要把每一位数字用链表存储起来，然后加起来，注意进位即可。 需要注意的有两点： - 使用头插，这样可以把数字逆过来，这样个位在前面，比较好处理
- 注意进位的问题， 这里使用了一个标志位来进行记录是否需要进位，每次相加都不断的进行更新
代码实现 public static void main(String[] args) { String num1 = '36578768657546342546560870899434'; String num2 = '254354657658768768543532424'; //先用链表把这两个大数存起来 LinkedList<Integer> list1 = new LinkedList<>(); LinkedList<Integer> list2 = new LinkedList<>(); for (int i = 0; i < num1.length(); i++) { list1.addFirst(num1.charAt(i)-'0'); } for (int i = 0; i < num2.length(); i++) { list2.addFirst(num2.charAt(i)-'0'); } //定义一个是否需要进位的标志 boolean bool = false; //定义结果集合 LinkedList<Integer> result = new LinkedList<>(); Iterator<Integer> iterator1 = list1.iterator(); Iterator<Integer> iterator2 = list2.iterator(); while(iterator1.hasNext() && iterator2.hasNext()) { Integer p = iterator1.next(); Integer q = iterator2.next(); int temp = p + q; if(bool) { temp += 1; bool = false; } if(temp > 9) { temp = temp%10; bool = true; } result.addFirst(temp); } //长的数字还没处理完 while (iterator1.hasNext()) { Integer temp = iterator1.next(); if(bool) { temp += 1; bool = false; } if(temp > 9) { temp = temp%10; bool = true; } result.addFirst(temp); } while (iterator2.hasNext()) { Integer temp = iterator2.next(); if(bool) { temp += 1; bool = false; } if(temp > 9) { temp = temp%10; bool = true; } result.addFirst(temp); } System.out.println(result); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
|
