关于单链表的题目及题解
第一题移除链表元素
这题大意是给一串链表，和一个数字key，如果链表中有和key相同的数组就删除，最后返回链表新的头结点。
我们该如何完成这道题？
首先我们应该考虑到如果这个链表为空怎么办？所以我们先要进行特别判断
if(head == null){ return null; }
题目中要求的是删除6这个数字
我们可以定义连个引用，首先让cur引用来判断是否是key，而prve这个引用是用来保存cur这个引用前一个引用的，这样就可以实现删除保存的数字是key这个节点了。
如果cur.val == key,则让prve的下个地址为cur的下个地址，如果不等于就把cur这个地址赋值给prve
具体我们看上面的图就可以理解了
class Solution { public ListNode removeElements(ListNode head, int val) { ListNode cur = head; ListNode prve = head; if(head == null) { return null; } while(cur != null) { if(cur.val == val) { prve.next = cur.next; }else { prve = cur; } cur = cur.next; } if(head.val == val) { return head.next; } return head; } }
第二题反转链表
这题大意是给我们一个链表，然后让我们逆序打印出来
通常有的人就是这样想的，我们可以先将链表中的数字都存到数组里面，然后打印，但这样不是真正的逆序，如果面试题是这样，我们这样操作的话，只会显得我们的水平很菜，所以我们应该从内部让它真正的实现逆序。
假设原来链表如上图所示，我们要变为如下：
首先肯定是将1的地址改为null，不然打印的时候就无法停止下来
class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head; ListNode prve = null; while(cur != null) { ListNode curNext = cur.next; cur.next = prve; prve = cur; cur = curNext; } return prve; } }
观察代码我们可以发现，这其实就是一个循环实现头插的过程。并且每行代码都是环环相扣的
第三题链表的中间节点
这题大意就是给一个链表，返回中间的节点，链表长度是个偶数，就返回第二个节点。
我们想到一个知识，如果速度是另一个速度的2倍，则路程也是，如果这样的话，我们定义一个快的指针，和一个慢的指针，这样当快的指针走到最后的时候，慢的指针是不是刚好走到中间那
class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) {//这个地方为什么要考虑fast.next呢？原来下面有个fast.next.next; fast = fast.next.next;//如果不考虑则会造成空指针异常 slow = slow.next; } return slow; } }
第四题链表中的倒数第k个节点
这题大意就是输入一个数字k，打印他的倒数第k个节点
我们这样想
假设一共有7个节点
打印倒数第3个节点前面隔了2个
打印倒数第5个节点前面隔了4个
打印倒数第7个节点前面隔了6个
我们是不是可以这样，首先定义两个节点，让快的节点先走k-1步，然后两个节点一起往前移动，
具体可以自己画图体会体会
注意这道题k的长度可能大于链表的长度
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { ListNode fast = head; ListNode slow = head; if(k < 0 || head == null) { return null; } while(k-1 != 0) { fast = fast.next; if(fast == null) { return null; } k --; } while(fast.next != null) { fast = fast.next; slow = slow.next; } return slow; } }
第五题将两个有序链表变为一个有序链表
合并两个有序，我们要重新开一个新的节点，来表示新的头
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newHead = new ListNode(-1); ListNode tmp = newHead; while(list1 != null && list2 != null) { if(list1.val < list2.val) { tmp.next = list1; list1 = list1.next; tmp = tmp.next; }else { tmp.next = list2; list2 = list2.next; tmp = tmp.next; } } if(list1 == null) { tmp.next = list2; } if(list2 == null) { tmp.next = list1; } return newHead.next; } }
第六题链表分割
这个题的大致意思就是输入一个数x，将所有小于x的数都放在左边，大于x的数都放在右边
public class Partition { public ListNode partition(ListNode Head, int x) { // write code here ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = Head; while(cur != null) { if(cur.val < x) { if(bs == null) { bs = cur;//表示x的左边 be =cur; }else { be.next = cur; be = be.next; } }else { if(as == null) { as = cur;//表示x的右边 ae = cur; }else { ae.next = cur; ae = ae.next; } } cur = cur.next; } if(bs == null) {//如果bs==null 则说明没有小于x的数 return as; } be.next = as; if(as != null) {//如果as有数，则需要将ae赋值为null,否则打印链表就不能停止 ae.next = null; } return bs; } }
以上6道题都是链表的基础题，自己掌握的也不算太精湛，各种细节可能处理不到希望各位指正。
还需要解决的问题：
就是明白为什么有的遍历链表条件是cur != null 而有的是 cur.next != null。
