链表

0. 结构体及必要说明

typedef struct LNode {
    int data;
    struct LNode *next;
}*LinkList;

1. 设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。

递归：head->next=return;

栈（head）：将值不等于 x 的节点用栈收集起来，收集完成后重新连接即可。

void del_x(LinkList &L,int x) {
    if(L==NULL)
        return;
    if(L.data==x) {
        LNode *temp=L;
        L=L->next;
        free(temp);
        del_x(L,x);
    } else
        del_x(L->next,x);
}
/*递归*/
ListNode* removeElements(ListNode* head, int val) {
    if (head == NULL)
        return head;
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}
/*Java：栈*/
public ListNode removeElements(ListNode head, int val) {
    Stack<ListNode> stack = new Stack<ListNode>();
    while (head != null) {
        if (head.val != val) {
            stack.push(head);
        }
        head = head.next;
    }
    while (!stack.isEmpty()) {
        stack.peek().next = head;
        head = stack.pop();
    }
    return head;
}

ps:书上的答案是这样写的，但是我不太理解的是如果这样的话，那值为x的结点L虽然删除了，可L的前驱结点没能指向其后继结点整个单链不就断了吗...

     破案了！由于该单链表不带头结点，第六行L为调用该函数的外层L->next，故这里实现了L->next=L->next->next，可自行尝试删除一条单链表的第1、2、3...个结点。

2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

双指针遍历引用（pre,cur,temp）:pre指向头结点，cur指向pre->next;

void del_x(LinkList &L,int x) {
    LNode *cur=L->next,*pre=L,*temp;
    while(cur!=NULL) {
        //这里的if可以任意指定内容 
        if(cur->data==x) {
            temp=cur;
            cur=cur->next;
            pre->next=cur;
            free(temp);
        } else {
            pre=cur;
            cur=cur->next;
        }
    }
}

3. L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

递归：没啥好说的；

void ReversePrint(LinkList L) {
    if(L->next!=NULL)
        ReversePrint(L->next);
    if(L!=NULL)//防止空链表的存在
        cout << L->data << endl;
}
/*带返回值*/
vector<int> v;
vector<int> ReversePrint(LinkNode *head) {
    if(L==NULL)
        return v;
    ReversePrint(head);
    v.push_back(head->data);
    return v;
}

4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的）。

四指针遍历引用（pre,p,minpre,minp）:先遍历，然后minpre->next=minp->next；

LinkList DelMin(LinkList &L) {
    LNode *pre=L,*p=L->next;
    LNode *minpre=L,*minp=L->next;
    while(p!=NULL) {
        if(p->data<minp->data) {
            minpre=pre;
            minp=p;
        }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
    return L;
}

5.试编写算法将不带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为0(1)。

指针反转（pre,head,next）：注意刚开始pre=NULL;

//指针反转
LinkList Reverse(LinkList &head) {
    ListNode *pre=NULL;
    ListNode *next;
    while(head) {
        next=head->next;
        head->next=pre;
        pre=head;
        head=next;
    }
    return pre;
}

6.有一个带头结点的单链表L，设计一个算法使其元素递增有序。

类似快排（pre,p,r）：1、把pre,p置成一个链表，r置成一个链表；2、p作为后者的cur,r=p->head；在前者找到要插入的位置的前驱结点pre,把p插到pre后面。

void Sort(LinkList &L) {
    LNode *p=L->next,*pre,*r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL) {
        r=p->next;
        pre=L;
        /*找到要插入位置的前驱结点pre*/
        while(pre->next!=NULL&&pre->next->data<p->data)
            pre=pre->next;
        /*把p插到pre后面*/
        p->next=pre->next;
        pre->next=p;
        /*p是另一条链表的cur*/
        p=r;
    }
}

7.请判断一个链表是否为回文链表。

栈(cur)：把链表元素放进栈里，用栈顶元素和head进行验证。

stack<int> s;
bool isPalindrome(ListNode* head) {
    stack<int> s;
    ListNode *cur = head;
    while(cur) {
        s.push(cur->val);
        cur = cur->next;
    }
    while(head) {
        if(head->val != s.top())
            return false;
        s.pop();
        head = head->next;
    }
    return true;
}

8.链表相交

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *tempA=headA,*tempB=headB;
    while(tempA!=tempB) {
        tempA=(tempA==NULL)? headB:tempA->next;
        tempB=(tempB==NULL)? headA:tempB->next;
    }
    return tempA;
}

9.删除任意链表中的重复元素

类似选择排序（cur,pre,next）：双指针遍历（pre,next），遇到与cur相等值的元素改变指向。

ListNode* deleteDuplicates(ListNode* head) {
    ListNode *cur = head;
    ListNode *pre = NULL;
    ListNode *next = NULL;
    while (cur != NULL) {
        pre = cur;
        next = cur->next;
        while (next != NULL) {
            if (cur->val == next->val) {
                pre->next = next->next;
            } else {
                pre = next;
            }
            next = next->next;
        }
        cur = cur->next;
    }
    return head;
}

10.将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1．如果两个链表中有一个为空，说明无须合并过程，返回另一个链表的头节点即可。

2．比较 head1 和 head2 的值，小的节点也是合并后链表的最小节点，这个节点无疑应该是 合并链表的头节点，记为 head。head 节点所在的链表为链表 1，另一个链表为链表 2。

3.  用cur1 和 cur2遍历，然后根据大小关系做出不同的调整（cur1 小于 cur2，不做调整，反之，让 pre 的 next 指针指向 cur2），同时用一个变量 pre 表示上次比较时值较小的节点。

4.  cur1先走完，就让pre->next接cur2；cur2先走完，散会！

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if(l1 == NULL || l2 == NULL)
        return l1==NULL? l2:l1;
    ListNode *head = l1->val < l2->val? l1 : l2;
    ListNode *cur1 = head == l1? l1 : l2;
    ListNode *cur2 = head == l1? l2 : l1;
    ListNode *pre = cur1;
    ListNode *next = NULL;
    while(cur1!=NULL && cur2!=NULL) {
        if(cur1->val <= cur2->val) {
            pre = cur1;
            cur1 = cur1->next;
        } else {
            next = cur2->next;
            pre->next = cur2;
            cur2->next = cur1;
            pre = cur2;
            cur2 = next;
        }
    }
    pre->next = cur1==NULL? cur2 : cur1;
    return head;
}

11.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

快慢指针（pre,cur）：注意：如果有两个中间结点，pre->next是第二个中间结点，pre是第一个中间结点。

ListNode* middleNode(ListNode* head) {
    /*当链表只有两个结点时*/
    if (head->next==NULL)
        return head;
    /*当链表只有两个结点时*/
    if (head->next->next == NULL) {
        return head->next;
    }
    ListNode *pre = head;
    ListNode *cur = head;
    while (cur->next != NULL && cur->next->next != NULL) {
        pre = pre->next;
        cur = cur->next->next;
    }
    /*如果有两个中间结点，pre->next是第二个中间结点，pre是第一个中间结点*/
    return cur->next!=NULL? pre->next:pre;
}

12.给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

TreeNode* sortedListToBST(ListNode* head) {
    if(!head)
        return NULL;
    else if(!head->next)
        return new TreeNode(head->val);
    ListNode *pre=head,*cur=pre->next,*next=cur->next;
    while(next && next->next){
        pre=pre->next;
        cur=pre->next;
        next=next->next->next;
    }
    pre->next=NULL;
    TreeNode *root = new TreeNode(cur->val);
    root->left = sortedListToBST(head);
    root->right = sortedListToBST(cur->next);
    return root;
}