【链表之练习题】

---

翻转链表

    //反转链表//实质上是把每一个节点头插法,原本第一个节点变成最后一个节点public ListNode reverseList(){//链表为空if (head == null){return null;}//链表只有一个节点if (head.next == null ){return head;}ListNode cur = this.head.next;//先定义cur的位置this.head.next =null;//再把head.next置为空while(cur != null){ListNode curNext =cur.next;//再定义curNext在cur后面cur.next =this.head;//让cur的下一个等于头节点，就能把cur头插到head前面head = cur;//head给到curcur = curNext;//cur再到curNext位置}return head;//返回头，就能返回一整个链表}
}

找到链表的中间节点

方法1：链表长度除以2得到中间节点

    //求链表中间节点//1.先求整个链表的长度//2.再求长度/2 就找到这个节点了public ListNode MiddleNode(){ListNode cur = this.head;int len = size();//让cur走到中间节点for (int i = 0; i < len/2; i++) {cur = cur.next;}return cur;}

方法2：
优化代码：快慢指针的引用

1. 当fast == null时，遍历结束

2. 当fast.next == null时，遍历结束

所以循环结束有两个条件：fast == null 或者 fast.next == null

    public ListNode MiddleNode1(){ListNode fast = this.head;ListNode slow = this.head;while (fast != null && fast.next != null ){fast = fast.next.next;slow = slow.next;}return slow;}

返回倒数第k个节点

    public ListNode findKthToTail(int k){//判断k的合法性if (k <= 0 || head == null){return null;}ListNode fast =head;ListNode slow =head;//先让fast走k-1步while(k-1 != 0){fast = fast.next;//如果k很大，这个判断可以让代码更高效if (fast == null){return null;}k--;}//slow和fast同时走//当fast.next =null时，slow已经在倒数第k个节点了while(fast.next != null){fast = fast.next;slow = slow.next;}return slow;}

合并两个有序链表

public class Test {//定义两个链表public static MySingleList.ListNode  mergeTwoLists(MySingleList.ListNode head1, MySingleList.ListNode head2){//定义一个虚拟节点，保存合并之后的新链表MySingleList.ListNode newH = new MySingleList.ListNode(-1);//newH节点是新链表的头节点，跟着记录串联之后的节点MySingleList.ListNode tmpH = newH;//当两个链表都不为空才能进入循环进行合并排序while(head1 != null && head2 != null){//当head1的值小于head2时，头节点tmpH的下一个节点就是连接小的那一个，然后head1再往后走一步           if (head1.val < head2.val){tmpH.next = head1;head1 = head1.next;}else{//当head2的值小于head1时，头节点tmpH的下一个节点就是连接小的那一个，然后head2再往后走一步  tmpH.next = head2;head2 = head2.next;}//无论进入那个语句，tmp都会往后走一步tmpH = tmpH.next;}//当head1没走完了，说明head2走完了，继续接着剩下的head1if(head1 != null){tmpH.next = head1;}//当head2没走完了，说明head1走完了，继续接着剩下的head2if(head2 != null){tmpH.next = head2;}//最后返回return tmpH;}public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.addLast(12);mySingleList.addLast(23);mySingleList.addLast(34);mySingleList.addLast(45);mySingleList.display();//打印数组MySingleList mySingleList2 = new MySingleList();mySingleList2.addLast(15);mySingleList2.addLast(24);mySingleList2.addLast(37);mySingleList2.addLast(166);mySingleList2.display();MySingleList.ListNode head = mergeTwoLists(mySingleList.head,mySingleList2.head);mySingleList.display();}

判断链表是否回文

1.先找到中间节点
2.翻转
3.前面往后走，后面往前走，值是否一样

    //判断是否回文public boolean chkPalindrome(){ListNode fast = head;ListNode slow = head;int len = size()/2;//5/2=2//1.找中间位置while(fast != null && fast.next != null){//fast先走俩步，slow再走一步fast = fast.next.next;slow = slow.next;}//2.翻转ListNode cur = slow.next;while(cur != null){ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//3.从前到后，从后到前while(head != slow){if (head.val != slow.val){return false;}//考虑偶数链表if (head.next == slow){return true;}head = head.next;slow = slow.next;}return true;}

注意

在写题过程中，我混淆了找中间节点和返回倒数第k个节点的方法

他们的区别其实是：
找中间节点 ：fast永远是slow的二倍，slow走一步，fast就走两步。

返回倒数第k个节点 ：fast和slow的关系不是固定的，fast走几步根据k-1得到，还有一个区别是，fast走了k-1步之后，slow走一步，fast也是走一步。