leetcode:链表题目

删除排序好的链表中重复的节点

快慢指针当发现有相等的节点的fast指针往前进直到不相等的节点。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == NULL)
            return head;
        ListNode* head_slow = head;
        ListNode* head_fast = head->next;
        while(head_fast != NULL)
        {
            if(head_fast->val == head_slow->val)
            {
                head_fast = head_fast->next;
                head_slow->next = head_fast;
                continue;
            }
            
            head_slow = head_slow->next;
            head_fast = head_fast->next;
        }
        
        return head;
    }
};

判断链表是否是回文

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if( head == NULL || head->next == NULL)
            return true;
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        //节点个数为偶数时结束标识为fast->next ==NULL,节点个数为奇数时结束标识为 fast->next->next == NULL
        while(fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow = slow->next;
        //将链表的后半部分进行反转
        slow = reverse(slow);
        
        while(slow != NULL)
        {
            if(slow->val != head->val)
                return false;
            
            slow = slow->next;
            head = head->next;
        }
        
        return true;       
    }
    
    ListNode* reverse(ListNode* head)
    {
        if (head == NULL)
            return NULL;
        ListNode* cur = head;
        ListNode* pre = NULL;
        ListNode* next = NULL;
        
        while(cur != NULL)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur =next;
        }    
        return pre;
    }
};

获取链表的中间节点

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next != NULL && fast->next->next != NULL )
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //偶数时slow再移动一个节点
        if(fast->next != NULL) slow = slow->next;
        
        return slow;
    }
};

两个链表相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(0); //占位节点，方便处理边界
        ListNode* res = result;
        int carry = 0;
        int l1_val = 0;
        int l2_val = 0;
        while(l1 != NULL || l2 != NULL)
        {
            l1_val = l1 ? l1->val : 0;
            l2_val = l2 ? l2->val : 0;
            int sum = carry + l1_val + l2_val;
            carry = sum/10;
            res->next = new ListNode(sum%10);
            res = res->next;
            
            if(l1 != NULL) l1 = l1->next;
            if(l2 != NULL)  l2 = l2->next;
        }
        
        if(carry > 0) res->next = new ListNode(1);
        return result->next;
    }
};

旋转链表

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* cur = head;
        int n = 0;
        while(cur != NULL)
        {
            n++;
            cur = cur->next;
        }
        
        k = k%n;  // k大于n时需要进行取余处理
        if(k==0) return head; //k等于0时不需要反转直接返回
        
        ListNode* slow_ptr = head;
        ListNode* fast_ptr = head;
        
       for(int i = k; i > 0 ; i--)
           fast_ptr = fast_ptr->next;
        while(fast_ptr->next != NULL)
        {
            fast_ptr = fast_ptr->next;
            slow_ptr = slow_ptr->next;
        }
        
        ListNode* new_head = slow_ptr->next;
        slow_ptr->next = NULL;
        fast_ptr->next = head;
        return new_head;
    }
};