【数据结构篇】链表

设计链表

• 在链表类中实现这些功能：

·get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
·addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
·addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
·addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
·deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

• 代码示例如下

typedef struct MyLinkedList_t
{
	int val;
	struct MyLinkedList_t *next;
} MyLinkedList;

/** Initialize your data structure here. */

MyLinkedList *myLinkedListCreate()
{
	MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList));
	obj->val = 0;
	obj->next = NULL;
	return obj;
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList *obj, int index)
{
	if (index < 0 || obj->next == NULL)
	{
		return -1;
	}
	
	int now = 0;
	MyLinkedList *listNow = obj->next;
	while (now < index)
	{
		if (listNow == NULL)
		{
			return -1;
		}

		listNow = listNow->next;
		now++;
	}

	if (listNow != NULL)
	{
		return listNow->val;
	}

	return -1;
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList *obj, int val)
{
	MyLinkedList *Node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
	Node->val = val;
	Node->next = NULL;

	if (obj->next == NULL)
	{
		obj->next = Node;
		return;
	}
	else
	{
		Node->next = obj->next;
		obj->next = Node;
	}
}

/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList *obj, int val)
{
	MyLinkedList *Node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
	Node->val = val;
	Node->next = NULL;

	MyLinkedList *nowList = obj;
	while (nowList->next != NULL)
	{
		nowList = nowList->next;
	}

	nowList->next = Node;
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)
{
	if (index <= 0)
	{
		myLinkedListAddAtHead(obj, val);
	}

	int now = 0;
	MyLinkedList *nowList = obj->next;
	while (nowList->next != NULL)
	{
		if (now == index - 1)
		{
			break;
		}
		nowList = nowList->next;
		now++;
	}

	if (index - 1 != now)
	{
		return;
	}

	MyLinkedList *Node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
	Node->val = val;
	Node->next = nowList->next;
	nowList->next = Node;
}

/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)
{
	MyLinkedList *r;
	if (index < 0 || obj->next == NULL)
	{
		return;
	}

	if (index == 0)
	{
		r = obj->next;
		obj->next = obj->next->next;
		free(r);
		return;
	}

	MyLinkedList *nowList = obj->next;
	int now = 0;
	while (nowList->next != NULL)
	{
		if (now == index - 1)
		{
			break;
		}
		nowList = nowList->next;
		now++;
	}

	if (now == index - 1 && nowList->next != NULL)
	{
		r = nowList->next;
		nowList->next = nowList->next->next;
		free(r);
	}
}

void myNodeFree(MyLinkedList *Node)
{
    if (Node->next != NULL)
{
    myNodeFree(Node->next);
    Node->next = NULL;
}
free(Node);
}

void myLinkedListFree(MyLinkedList *obj)
{//从最后一个结点向前逐渐释放，这里用递归实现
    myNodeFree(obj);
}

环形链表

• 可以用快慢指针判断是否有环（有环返回真，无环返回假）

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

bool hasCycle(struct ListNode *head) {
        if(head==NULL) return false;
        ListNode *f=head;
        ListNode *s=head;
        do{
            if(f->next==NULL||f->next->next==NULL) return false;
            f=f->next->next;//f为走两步的快指针
            s=s->next;//s为走一步的慢指针
        }while(f!=s);
        return true;//如果有环一定能相遇
    }

• 如果要返回==入环的第一个结点==呢？

可以这样分析：
1 慢指针走过的路程为a(头结点到环入口的距离)+b(慢指针在环内的距离)
2 快指针走过的路程为a+b+c(相遇点到换入口的距离)+b
3 因为快指针速度是慢指针的两倍，所以可以导出a=c
4 所以只要再安排一个位于头结点的指针和慢指针同时出发，它们的相遇位置即为环入口

struct ListNode *detectCycle(struct ListNode *head) {
        if(head==NULL) return false;
        struct ListNode *f=head;
        struct ListNode *s=head;
        do{
            if(f->next==NULL||f->next->next==NULL) return false;
            f=f->next->next;//f为走两步的快指针
            s=s->next;//s为走一步的慢指针
        }while(f!=s);
       struct ListNode*p=head;
       while(p!=s)
       {
           p=p->next;
           s=s->next;
       }
        return p;
}

回文链表

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr != NULL) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}//反转链表

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

bool isPalindrome(struct ListNode* head) {
    if (head == NULL) {
        return true;
    }

    // 找到前半部分链表的尾节点并反转后半部分链表
    struct ListNode* firstHalfEnd = endOfFirstHalf(head);
    struct ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

    // 判断是否回文
    struct ListNode* p1 = head;
    struct ListNode* p2 = secondHalfStart;
    bool result = true;
    while (result && p2 != NULL) {
        if (p1->val != p2->val) {
            result = false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    // 还原链表并返回结果
    firstHalfEnd->next = reverseList(secondHalfStart);
    return result;
}

持续更新中