链表OJ练习

---

---

一、链表的删除

【题目】给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
【分析】

1. 需要判断删除节点是否为空

            if(head == null){return null;}

2. 删除头节点

            if(head.val == val){head = head.next;}

3. 删除中间节点

            ListNode prev = head; //待删除节点的前一个节点ListNode cur = head.next; //待删除节点while(cur != null) {if(cur.val == val) {//找到了待删除节点prev.next = cur.next;cur = prev.next;}else {//当前值不是需要删除的值,则只需更新 prev 和 curprev = prev.next;cur = cur.next;}}

• 注意：此方法忽略了第二个元素也是目标元素的情况，故应该循环判断头结点是否是要删除的节点，为了解决这个问题，最简单的方法是调整删除头结点和删除中间节点的顺序

class ListNode {int val = 0;ListNode next = null;public ListNode() {}public ListNode(int val) {this.val = val;this.next = null;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

public class Solution {public ListNode removeElements(ListNode head, int val) {//在线oj提供的链表默认不带傀儡节点//删除时需要考虑待删除节点是否是头结点的情况//删除其他节点是需要找到该节点的前一个节点//删除头结点为空的节点if(head == null){return null;}//删除一般节点ListNode prev = head; //待删除节点的前一个节点ListNode cur = head.next; //待删除节点while(cur != null) {if(cur.val == val) {//找到了待删除节点prev.next = cur.next;cur = prev.next;}else {//当前值不是需要删除的值,则只需更新 prev 和 curprev = prev.next;cur = cur.next;}}//先删除中间节点，再删除头结点if(head.val == val){head = head.next;}return head;}}

二、反转单链表

【题目】给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
【分析】逆置的过程中需要先设定三个引用，使用prevNode记录前一个节点，curNode记录当前节点，nextNode记录下一个节点。核心操作是curNode.next = prevNode；核心代码为将当前位置的节点指向改变，使其指向前一个节点。

• step0：
• step1：
  
• step2：
  
  

    public ListNode reverseList(ListNode head) {//写代码的时候都要考虑到特殊情况if (head == null){return null;}//链表中只有一个节点if (head.next == null){return head;}//处理一般情况ListNode newHead = null;ListNode prevNode = null;ListNode curNode = head;ListNode nextNode = curNode.next;while (curNode != null){if (nextNode == null){//curNode 指向了链表的最后一个节点//此节点则为逆置链表的头结点newHead = curNode;}//为了保证 nextNode 不会失效，需要初始化 nextNode 的值nextNode = curNode.next;//更新指向curNode.next = prevNode;//更新其他引用的位置prevNode = curNode;curNode = nextNode;}return newHead;}

三、返回中间节点

【题目】给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
【分析】oj题目一般默认不带傀儡节点。若要返回中间节点，则需要先求出总长度，然后对总长度除以二，设置引用从头开始遍历，遍历的步数为总长度的一半时，即可得出我们需要的结果。

class ListNode{int val;ListNode next;public ListNode(int v){val = v;}
}public class LinkedList {//求链表长度public int getLength(ListNode head){//遍历链表即可int length = 0;for (ListNode cur = head;cur != null;cur = cur.next){length++;}return length;}public ListNode middleNode(ListNode head) {//虽然题目给出的链表是非空单链表，但是在实际开发过程中，需要加上非空判断if (head == null){return null;}//求链表的长度int length = getLength(head);//求引用走的步数int steps = length / 2;ListNode cur = head;for (int i = 0;i < steps;i ++){cur = cur.next;}return cur;}
}

四、求倒数指定节点

【题目】输入一个链表，输出该链表中倒数第k个结点
【分析】k的最大值就是单链表的长度length；又考虑到单链表只能从前往后遍历，不能从后往前遍历，故要想得到倒数第k个节点，则需要从头（head）开始走length-k步。

class ListNode{int val;ListNode next;public ListNode(int v){val = v;}
}//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，
//则返回第二个中间结点
public class LinkedList {//求链表长度public int getLength(ListNode head){//遍历链表即可int length = 0;for (ListNode cur = head;cur != null;cur = cur.next){length++;}return length;}//输入一个链表，输出该链表中倒数第k个结点public ListNode  FindKthToTail(ListNode head,int k) {//判断头结点是否为空if (head == null){return null;}if (k <= 0){return null;}int length = getLength(head);if (k > length){return null;}//若要的到倒数第 k 个节点，就需要让引用从头开始遍历走 k 步。int steps = length -k;ListNode cur = head;for (int i = 0;i < steps;i++){cur = cur.next;}//cur指向了倒数第 k 个节点return cur;}
}

五、链表有序合并

【题目】将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
【分析】先设置两个引用分别指向两个链表的头结点。依次循环比较其大小，使值大者插入结果链表的末尾并更新引用指向下一个节点。任何一个引用到达链表末尾，就算循环结束。

• 不带傀儡节点的时候需要对头结点是否为空做分类讨论

    //链表的有序合并（不带傀儡节点）public ListNode mergeTwoLists(ListNode list1, ListNode list2){if (list1 == null){return list2;}if(list2 == null){return list1;}//两个链表都非空，则进行合并ListNode cur1 = list1;ListNode cur2 = list2;//创建的新链表保存合并结果ListNode newHead = null;//后续要频繁进行尾插，为了尾插方便，用改变量将尾部节点标记//虽然链表一般都用头结点来表示，但是也可以用引用记录其他节点。ListNode newTail = null;//循环遍历两个链表，并比较。任意引用到达链表末尾，都算循环结束while(cur1 != null && cur2 != null){if(cur1.val < cur2.val){//把 cur1 插入到新链表末尾if (newTail == null){//针对空链表插入newHead = cur1;newTail = newHead;}else {//针对非空链表的插入newTail.next = cur1;newTail = newTail.next;}}else{//把 cur2 插入到新链表末尾if(newTail == null){//针对空链表的插入newHead = cur2;newTail = newHead;}else {//针对非空链表的插入newTail.next = cur2;newTail = newTail.next;}}}}

• 带傀儡节点

    //链表的有序合并（带傀儡节点）public ListNode mergeTwoLists(ListNode list1, ListNode list2){if (list1 == null) {return list2;}if (list2 == null) {return list1;}//两个链表都非空，则进行合并ListNode cur1 = list1;ListNode cur2 = list2;//创建的新链表保存合并结果ListNode newHead = new ListNode(0); //傀儡节点//后续要频繁进行尾插，为了尾插方便，用改变量将尾部节点标记//虽然链表一般都用头结点来表示，但是也可以用引用记录其他节点。ListNode newTail = newHead;//循环遍历两个链表，并比较。任意引用到达链表末尾，都算循环结束while (cur1 != null && cur2 != null) {if (cur1.val < cur2.val) {//把 cur1 插入到新链表末尾newTail.next = cur1;cur1 = cur1.next;  //更新循环变量} else {//把 cur2 插入到新链表末尾,针对非空链表的插入newTail.next = cur2;cur2 = cur2.next;  //更新循环变量}newTail = newTail.next;}//当上述循环结束时，意味着一定有一个引用已经先到达链表末尾，// 此时只需要把另外一个链表的尾部节点返回即可if(cur1 == null){newTail.next = cur2;}else {newTail.next = cur1;}//newHead是带傀儡节点的链表，返回的链表是不带傀儡节点return newHead.next;}
}

六、按照给定节点分类

【题目】现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
【分析】首先，遍历链表。然后将链表中标的元素和节点处的值做大小 比较，将得到的较小的值放到一个新的链表的中，将得到的较大值放到另外一个新的链表中吗，最后将两个新的链表拼接在一块即可。

public ListNode partition(ListNode pHead, int x) {//判断链表头结点是否为空if (pHead == null){return null;}//链表只有一个节点if(pHead.next == null){return pHead;}//处理一般情况，创建两个新链表，存储两部分结果//为了方便尾插，此处使用带傀儡节点的链表ListNode smallHead = new ListNode(0);ListNode smallTail = smallHead;ListNode largeHead = new ListNode(0);ListNode largeTail = largeHead;for (ListNode cur = pHead;cur != null;cur = cur.next){if(cur.val < x){//插入到 smallHead 末尾
//                smallHead.next = cur;//采用此方法的尾插是在原来的链表基础上进行操作的，//因此为了不破坏原理的链表，设置一个新的链表对其进行尾插操作smallHead.next = new ListNode(cur.val);smallHead = smallTail.next;}else {//插入到 largeHead 末尾largeHead.next = new ListNode(cur.val);largeHead = largeTail.next;}}//代码运行到此处，原链表被拆分成两个链表。//第一部分是小于x的元素//第二部分是大于x的元素//最后一步只需要将两部分连接成一块（首（大的）尾（小的）相接）即可smallTail.next = largeHead.next;return smallHead;}