Anaconda env set

怎么得到链表的整个长度并取得中间值

快慢指针遍历链表

ListNode* middleNode(ListNode* head) {
       ListNode * slow = head;
       ListNode * fast = head;
       while(fast != NULL&&fast->next!=NULL){
       
               fast = fast->next->next;
               slow = slow->next;
           }
           
       
       return slow;
       
   }

链表中元素的删除

最主要的是分清要删除的节点是否是头结点，尾结点和普通节点

public:
    ListNode* removeElements(ListNode* head, int val) {//在原链表进行操作，需要考虑是否是头结点是否是尾结点
   //if(head==NULL) return head;
        ListNode  * tmp = head ;
        ListNode * pre = tmp;
        
        while(tmp!=NULL){
            if(tmp->val==val){
                if(tmp ==head){
                    head = tmp->next;
                    tmp = head;
                if(head==NULL) return head;
                    continue;
                }else if(tmp->next==NULL){
                    pre->next = NULL;
                    return head;
                }else{
                      pre->next = tmp->next;
                tmp = tmp->next;
                }              
            }else{
                pre = tmp;
                tmp = tmp->next;
               
            }
        }
        return head;
    }

链表的原位置翻转

ListNode* reverseList(ListNode* head) {
        ListNode * cur = head;
        ListNode * pre = NULL;//注意此处不能将pre的初值赋值为head，不然会形成环状链表
        ListNode * tmp = NULL;

        while(cur){
            tmp = cur->next;//在赋值运算符的右边，->next看做一个节点
            cur->next = pre ;//在赋值运算符的左边，cur->next看做是对cur指向什么节点进行操作
            pre = cur;//注意这一步操作不能和下一个操作换位置，是先把当前节点赋值给pre作为下次操作的前驱节点，然后才将上面保存的下一个待翻转的节点赋值给当前节点
            cur = tmp;
           
        }
        return pre;
    }

递归解法

不是很容易理解的递归解法

递归的两个条件：

终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是head的下一个节点指向head 递归函数那句

head.next.next = head
递归函数中每次返回的cur其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。

直接看最后一层循环终止，此时head = 4，cur =5；head->next是5，将它的指向指向此时的head节点4，并且将4 指向空，返回节点5，此时链表结构是5->4->NULL;返回到第三层递归 head 是3，head->next 为节点 4,且4指向NULL；
第三层的cur 等于第四层的cur仍然是5？；此时返回 head->next = 4 将其next指向3，3指向NULL

class Solution {
	public ListNode reverseList(ListNode head) {
		//递归终止条件是当前为空，或者下一个节点为空
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		//这里请配合动画演示理解
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空
		//所以head.next.next 就是5->4
		head.next.next = head;
		//防止链表循环，需要将head.next设置为空
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点
		return cur;
	}
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 583614868@qq.com