C语言学习第二十八天（关于单链表操作的一些OJ题目）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val == val)
        {
            struct ListNode* next = cur->next; 
            free(cur);

            if(prev)
                prev->next = next;
            else
                head = next;
                cur = next;
        }
        else
        {
           prev = cur;
           cur = cur->next;
        }
    }
    return head;
}

?还有一种解法如下：

struct ListNode* removeElements(struct ListNode* head, int val)
{
	struct ListNode* newhead = NULL, *tail = NULL;
	struct ListNode* cur = head;
	while (cur)
	{
		//不是val的节点取下来尾插
		if (cur->val != val)
		{
			//尾插
			if (tail == NULL)
			{
				newhead = tail = cur;
			}
			else
			{
				tail->next = cur;
				tail = tail->next;
			}
			cur = cur->next;
		}
		else
		{
			struct ListNode* tmp = cur;
			cur = cur->next;
			free(tmp);
		}
	}
	if (tail)
		tail->next = NULL;
	return newhead;
}

?代码如下：
?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3 -> next;
        }
    }
    return n1;

}

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

?

?代码如下：
?

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    
    struct ListNode*slow = pListHead,*fast = pListHead;
    //fast先走k步
    while(k--)
    {
        if(fast==NULL)
        {
            return NULL;
        }
       fast = fast->next;
    }
    //同时走
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
    
}

代码如下：

?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }   
    if(list2==NULL)
    return list1;
    struct ListNode* tail = NULL;
    struct ListNode* head = NULL;
    while(list1&&list2)
    {
        if (list1->val < list2->val)
        {
            if (tail == NULL)
            {
                tail = head = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail -> next;
            }
            list1 = list1->next;
        }
         else
        {
            if (tail == NULL)
            {
                tail = head = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail -> next;
            }
            list2 = list2->next;
        }
    }
    if(list1)
    tail->next = list1;
    if(list2)
    tail->next = list2;
    return head;
}

代码如下：?

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
        struct ListNode*next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

struct ListNode*middleNode(struct ListNode* head){
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
class PalindromeList {
  public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = middleNode(A);
        struct ListNode* rhead = reverseList(mid);
        while(A&&rhead)
        {
            if(A->val!=rhead->val)
            return false;
            A = A->next;
            rhead = rhead -> next;
        }
        return true;
    }
};

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    int len1 = 0;
    int len2 = 0;
    while(cur1)
    {
        cur1 = cur1->next;
        len1++;
    }
    while(cur2)
    {
        cur2 = cur2->next;
        len2++;
    }
    int n = abs(len1-len2);
    struct ListNode* head1 = headA;
    struct ListNode* head2 = headB;
    if(len1>len2)
    {
         while(n--)
         {
             head1=head1->next;
         }
    }else{
        while(n--)
        {
            head2 = head2->next;
        }
    }
    while(head1!=head2)
    {
        head1 = head1->next;
        head2 = head2->next;
    }
    return head1;
}

?

?代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast&&fast->next)
    {
        //if(fast)
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode*MeetPoint = NULL;
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
        {
            MeetPoint = fast; 
            break;
        }
    }
    if(MeetPoint==NULL){
        return NULL;
    }
    else
    {
        fast = MeetPoint;
        slow = head;
        while(fast!=slow)
        {
            fast = fast->next;
            slow = slow->next;
            
        }
        return fast;
    }
}